Trees with unique minimum global offensive alliance
RAIRO. Operations Research, Tome 55 (2021), pp. S863-S872

Let G = (V, E) be a simple graph. A non-empty set D ⊆ V is called a global offensive alliance if D is a dominating set and for every vertex ν in V − D, |$$ [ν] ∩ D|≥|$$ [ν] − D|. The global offensive alliance number is the minimum cardinality of a global offensive alliance in G. In this paper, we give a constructive characterization of trees having a unique minimum global offensive alliance.

DOI : 10.1051/ro/2020017
Classification : 05C69, 05C70
Keywords: Tree, domination, global offensive alliance, characterization 
@article{RO_2021__55_S1_S863_0,
     author = {Bouzefrane, Mohamed and Bouchemakh, Isma and Zamime, Mohamed and Ikhlef-Eschouf, Noureddine},
     title = {Trees with unique minimum global offensive alliance},
     journal = {RAIRO. Operations Research},
     pages = {S863--S872},
     year = {2021},
     publisher = {EDP-Sciences},
     volume = {55},
     doi = {10.1051/ro/2020017},
     mrnumber = {4223086},
     zbl = {1469.05126},
     language = {en},
     url = {https://www.numdam.org/articles/10.1051/ro/2020017/}
}
TY  - JOUR
AU  - Bouzefrane, Mohamed
AU  - Bouchemakh, Isma
AU  - Zamime, Mohamed
AU  - Ikhlef-Eschouf, Noureddine
TI  - Trees with unique minimum global offensive alliance
JO  - RAIRO. Operations Research
PY  - 2021
SP  - S863
EP  - S872
VL  - 55
PB  - EDP-Sciences
UR  - https://www.numdam.org/articles/10.1051/ro/2020017/
DO  - 10.1051/ro/2020017
LA  - en
ID  - RO_2021__55_S1_S863_0
ER  - 
%0 Journal Article
%A Bouzefrane, Mohamed
%A Bouchemakh, Isma
%A Zamime, Mohamed
%A Ikhlef-Eschouf, Noureddine
%T Trees with unique minimum global offensive alliance
%J RAIRO. Operations Research
%D 2021
%P S863-S872
%V 55
%I EDP-Sciences
%U https://www.numdam.org/articles/10.1051/ro/2020017/
%R 10.1051/ro/2020017
%G en
%F RO_2021__55_S1_S863_0
Bouzefrane, Mohamed; Bouchemakh, Isma; Zamime, Mohamed; Ikhlef-Eschouf, Noureddine. Trees with unique minimum global offensive alliance. RAIRO. Operations Research, Tome 55 (2021), pp. S863-S872. doi: 10.1051/ro/2020017

H. Balakrishnan, A. Cami, 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

M. Blidia, M. Chellali, R. Lounes and F. Maffray, Characterizations of trees with a unique minimum locating-dominating sets. J. Combin. Math. Combin. Comput. 76 (2011) 225–232. | MR | Zbl

M. Bouzefrane and M. Chellali, On the global offensive alliance number of a tree. Opuscula Math. 29 (2009) 223–228. | MR | Zbl | DOI

M. Bouzefrane and M. Chellali, A note on global alliances in trees. Opuscula Math. 31 (2011) 153–158. | MR | Zbl | DOI

M. Bouzefrane and S. Ouatiki, On the global offensive alliance in unicycle graphs. AKCE Int. J. Graphs Comb. 15 (2018) 72–78. | MR | Zbl | DOI

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

M. Chellali and T. W. Haynes, Trees with unique minimum paired domination sets. Ars Combin. 73 (2004) 3–12. | MR | Zbl

M. Chellali and T. W. Haynes, A characterization of trees with unique minimum double domination sets. Util. Math. 83 (2010) 233–242. | MR | Zbl

M. Chellali and N. J. Rad, Trees with unique Roman dominating functions of minimum weight. Discrete Math. Algorithms Appl. 06 (2014) 1450038. | MR | Zbl | DOI

M. Chellali and L. Volkmann, Independence and global offensive alliance in graphs. Australas. J. Combin. 47 (2010) 125–131. | MR | Zbl

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

H. Fernau, J. A. Rodríguez-Velázquez and J. M. Sigarreta, Offensive r -alliances in graphs. Discrete Appl. Math. 157 (2009) 177–182. | MR | Zbl | DOI

M. Fischermann, Block graphs with unique minimum dominating sets. Discrete Math. 240 (2001) 247–251. | MR | Zbl | DOI

M. Fischermann and U. D. E. Triesch, Domination parameters and their unique realizations, Ph.D. thesis. Techn. Hochsch. Bibl. (2002).

M. Fischermann and L. Volkmann, Unique minimum domination in trees. Australas. J. Combin. 25 (2002) 117–124. | MR | Zbl

M. Fischermann and L. Volkmann, Cactus graphs with unique minimum dominating sets. Util. Math. 63 (2003) 229–238. | MR | Zbl

M. Fischermann and L. Volkmann, Unique independence, upper domination and upper irredundance in graphs. J. Combin. Math. Combin. Comput. 47 (2003) 237–249. | MR | Zbl

M. Fischermann, D. Rautenbach and L. Volkmann, Maximum graphs with a unique minimum dominating set. Discrete Math. 260 (2003) 197–203. | MR | Zbl | DOI

M. Fischermann, L. Volkmann and I. Zverovich, Unique irredundance, domination, and independent domination in graphs. Discrete Math. 305 (2005) 190–200. | MR | Zbl | DOI

M. Fraboni and N. Shank, Maximum graphs with unique minimum dominating set of size two. Australas. J. Combin. 46 (2010) 91–99. | MR | Zbl

G. Gunther, B. Hartnell, L. Markus and D. Rall, Graphs with unique minimum dominating sets. In: Vol. 101 of Proc. 25th S.E. Int. Conf. Combin., Graph Theory, and Computing, Congr. Numer., Springer, New York, NY (1994) 55–63. | MR | Zbl

A. Harutyunyan, Some bounds on global alliances in trees. Discrete Appl. Math. 161 (2013)1739–1746. | MR | Zbl | DOI

A. Harutyunyan, Global offensive alliances in graphs and random graphs. Discrete Appl. Math. 164 (2014) 522–526. | MR | Zbl | DOI

T. W. Haynes and M. A. Henning, Trees with unique minimum total dominating sets. Discuss. Math. Graph Theory 22 (2002) 233–246. | MR | Zbl | DOI

T. W. Haynes, S. T. Hedetniemi and P. J. Slater, Fundamentals of Domination in graphs. Marcel Dekker, New York, NY (1998). | MR | Zbl

T. W. Haynes, S. T. Hedetniemi and P. J. Slater, Domination in Graphs: Advanced Topics. Marcel Dekker, New York, NY (1998). | MR | Zbl

J. Hedetniemi, On unique minimum dominating sets in some cartesian product graphs. Discuss. Math. Graph Theory 34 (2015) 615–628. | MR | Zbl | DOI

J. Hedetniemi, On unique minimum dominating sets in some repeated cartesian products. Australas. J. Combin. 62 (2015) 91–99. | MR | Zbl

J. Hedetniemi, On unique realizations of domination chain parameters. J. Combin. Math. Combin. Comput. 101 (2017) 193–211. | MR | Zbl

G. Hopkins and W. Staton, Graphs with unique maximum independent sets. Discrete Math. 57 (1985) 245–251. | MR | Zbl | DOI

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

K. Ouazine, H. Slimani and A. Tari, Alliances in graphs: parameters, properties and applications-a survey. AKCE Int. J. Graphs Comb. 15 (2018) 115–154. | MR | Zbl | DOI

N. J. Rad, A note on the global offensive alliances in graphs. Discrete Appl Math 250 (2018) 373–337. | MR | Zbl | DOI

J. A. Rodríguez-Velázquez and J. M. Sigarreta, Global offensive alliances in graphs. Electron. Notes Discrete Math. 25 (2006) 157–164. | MR | Zbl | DOI

J. A. Rodríguez-Velázquez and J. M. Sigarreta, Spectral study of alliances in graphs. Discuss. Math. Graph Theory 27 (2007) 143–157. | MR | Zbl | DOI

W. Siemes, J. Topp and L. Volkmann, On unique independent sets in graphs. In Vol. 131 of Discrete Math. Elsevier, New York, NY (1994) 279–285. | MR | Zbl | DOI

J. Topp, Graphs with unique minimum edge dominating sets and graphs with unique maximum independent sets of vertices. Discrete Math. 121 (1993) 199–210. | MR | Zbl | DOI

I. G. Yero and J. A. Rodriguez-Velázquez, Computing global offensive alliances in Cartesian product graphs. Discrete Appl. Math. 161 (2013) 284–293. | MR | Zbl | DOI

Cité par Sources :