no. 2
A lower bound on the global powerful alliance number in trees
RAIRO. Operations Research, Tome 55 (2021) no. 2, pp. 495-503

For a graph G = (V, E), a set D ⊆ V is a dominating set if every vertex in V − D is either in D or has a neighbor in D. A dominating set D is a global offensive alliance (resp. a global defensive alliance) if for each vertex v in V − D (resp. v in D) at least half the vertices from the closed neighborhood of v are in D. A global powerful alliance is both global defensive and global offensive. The global powerful alliance number γ$$(G) is the minimum cardinality of a global powerful alliance of G. We show that if T is a tree of order n with l leaves and s support vertices, then γ pa (T)≥3n-2l-s+2 5. Moreover, we provide a constructive characterization of all extremal trees attaining this bound.

Reçu le :
Accepté le :
Première publication :
Publié le :
DOI : 10.1051/ro/2021028
Classification : 05C69, 05C05
Keywords: Domination, global powerful alliance, trees 
@article{RO_2021__55_2_495_0,
     author = {Ouatiki, Saliha and Bouzefrane, Mohamed},
     title = {A lower bound on the global powerful alliance number in trees},
     journal = {RAIRO. Operations Research},
     pages = {495--503},
     year = {2021},
     publisher = {EDP-Sciences},
     volume = {55},
     number = {2},
     doi = {10.1051/ro/2021028},
     mrnumber = {4238789},
     zbl = {1468.05216},
     language = {en},
     url = {https://www.numdam.org/articles/10.1051/ro/2021028/}
}
TY  - JOUR
AU  - Ouatiki, Saliha
AU  - Bouzefrane, Mohamed
TI  - A lower bound on the global powerful alliance number in trees
JO  - RAIRO. Operations Research
PY  - 2021
SP  - 495
EP  - 503
VL  - 55
IS  - 2
PB  - EDP-Sciences
UR  - https://www.numdam.org/articles/10.1051/ro/2021028/
DO  - 10.1051/ro/2021028
LA  - en
ID  - RO_2021__55_2_495_0
ER  - 
%0 Journal Article
%A Ouatiki, Saliha
%A Bouzefrane, Mohamed
%T A lower bound on the global powerful alliance number in trees
%J RAIRO. Operations Research
%D 2021
%P 495-503
%V 55
%N 2
%I EDP-Sciences
%U https://www.numdam.org/articles/10.1051/ro/2021028/
%R 10.1051/ro/2021028
%G en
%F RO_2021__55_2_495_0
Ouatiki, Saliha; Bouzefrane, Mohamed. A lower bound on the global powerful alliance number in trees. RAIRO. Operations Research, Tome 55 (2021) no. 2, pp. 495-503. doi: 10.1051/ro/2021028

[1] M. Bouzefrane , On alliances in graphs, Magister memory. University of Blida, Algeria (2010).

[2] R. C. Brigham , R. D. Dutton , T. W. Haynes and S. T. Hedetniemi , Powerful alliances in graphs. Discrete Math. 309 (2009) 2140–2147. | MR | Zbl | DOI

[3] A. Cami , H. Balakrishnan , N. Deo and R. D. Dutton , On the complexity of finding optimal global alliances. J. Combin. Math. Combin. Comput. 58 (2006) 23–31. | MR | Zbl

[4] M. Chellali , Offensive alliances in bipartite graphs. J. Combin. Math. Combin. Comput. 73 (2010) 245–255. | MR | Zbl

[5] M. Chellali and T. Haynes , Global alliances and independence in trees. Discuss. Math. Graph Theory 27 (2007) 19–27. | MR | Zbl | DOI

[6] O. Favaron , G. Fricke , W. Goddard , S. M. Hedetniemi , S. T. Hedetniemi , P. Kristiansen , R. C. Laskar and D. R. Skaggs , Offensive alliances in graphs. Discuss. Math. Graph Theory 24 (2004) 263–275. | MR | DOI

[7] A. Harutyunyan , A fast algorithm for powerful alliances in trees. In: International Conference on Combinatorial Optimisation and Applications, COCOA (2010) 31–40. | MR | Zbl | DOI

[8] S. M. Hedetniemi , S. T. Hedetniemi and P. Kristiansen , Alliances in graphs. J. Combin. Math. Combin. Comput. 48 (2004) 157–177. | MR | Zbl

[9] S. Ouatiki , On the upper global powerful alliance number in trees. Accepted in Ars Combinatoria. | MR | Zbl

Cité par Sources :