Global defensive k -alliances in directed graphs: combinatorial and computational issues
RAIRO - Operations Research - Recherche Opérationnelle, Tome 54 (2020) no. 4, pp. 1027-1040.

In this paper we define the global defensive k-alliance (number) in a digraph D, and give several bounds on this parameter with characterizations of all digraphs attaining the bounds. In particular, for the case k = −1, we give a lower (an upper) bound on this parameter for directed trees (rooted trees). Moreover, the characterization of all directed trees (rooted trees) for which the equality holds is given. Finally, we show that the problem of finding the global defensive k-alliance number of a digraph is NP-hard for any suitable non-negative value of k, and in contrast with it, we also show that finding a minimum global defensive (−1)-alliance for any rooted tree is polynomial-time solvable.

DOI : 10.1051/ro/2019049
Classification : 05C20, 05C69
Mots-clés : Global defensive $$-alliance number, dominating set, $$-order-sum number, rooted tree, directed tree
@article{RO_2020__54_4_1027_0,
     author = {Mojdeh, Doost Ali and Samadi, Babak and Yero, Ismael G.},
     title = {Global defensive $k$-alliances in directed graphs: combinatorial and computational issues},
     journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
     pages = {1027--1040},
     publisher = {EDP-Sciences},
     volume = {54},
     number = {4},
     year = {2020},
     doi = {10.1051/ro/2019049},
     mrnumber = {4100699},
     language = {en},
     url = {http://www.numdam.org/articles/10.1051/ro/2019049/}
}
TY  - JOUR
AU  - Mojdeh, Doost Ali
AU  - Samadi, Babak
AU  - Yero, Ismael G.
TI  - Global defensive $k$-alliances in directed graphs: combinatorial and computational issues
JO  - RAIRO - Operations Research - Recherche Opérationnelle
PY  - 2020
SP  - 1027
EP  - 1040
VL  - 54
IS  - 4
PB  - EDP-Sciences
UR  - http://www.numdam.org/articles/10.1051/ro/2019049/
DO  - 10.1051/ro/2019049
LA  - en
ID  - RO_2020__54_4_1027_0
ER  - 
%0 Journal Article
%A Mojdeh, Doost Ali
%A Samadi, Babak
%A Yero, Ismael G.
%T Global defensive $k$-alliances in directed graphs: combinatorial and computational issues
%J RAIRO - Operations Research - Recherche Opérationnelle
%D 2020
%P 1027-1040
%V 54
%N 4
%I EDP-Sciences
%U http://www.numdam.org/articles/10.1051/ro/2019049/
%R 10.1051/ro/2019049
%G en
%F RO_2020__54_4_1027_0
Mojdeh, Doost Ali; Samadi, Babak; Yero, Ismael G. Global defensive $k$-alliances in directed graphs: combinatorial and computational issues. RAIRO - Operations Research - Recherche Opérationnelle, Tome 54 (2020) no. 4, pp. 1027-1040. doi : 10.1051/ro/2019049. http://www.numdam.org/articles/10.1051/ro/2019049/

[1] J. Bang-Jensen and G. Gutin, Digraphs: Theory, Algorithms and Applications. Springer Monographs in Mathematics. Springer-Verlag, London Ltd., London (2007). | Zbl

[2] H. Fernau and J.A. Rodríguez-Velázquez, A survey on alliances and related parameters in graphs. Electron. J. Graph Theory Appl. 2 (2014) 70–86. | DOI | MR | Zbl

[3] G.W. Flake, S. Lawrence and C.L. Giles, Efficient identification of web communities. In: Proceedings of the sixth ACM SIGKDD international conference on Knowledge discovery and data mining. KDD ‘00, ACM, New York, NY, USA (2000). | DOI

[4] Y. Fu, Dominating set and converse dominating set of a directed graph. Am. Math. Mon. 75 (1968) 861–863. | DOI | MR | Zbl

[5] M.R. Garey and D.S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman & Co., New York, USA (1979). | Zbl

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

[7] L.H. Jamieson, Algorithms and complexity for alliances and weighted alliances of varoius types, Ph.D. thesis. Clemson University, Clemson, SC, USA (2007).

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

[9] D.A. Mojdeh, B. Samadi and I.G. Yero, Global offensive k -alliances in digraphs. Preprint arXiv: [math.CO] (2019). | arXiv | MR

[10] E.F. Moore, The shortest path through a maze. In: Proceedings of the International Symposium on the Theory of Switching. Harvard University Press (1959) 285–292. | MR

[11] 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. | DOI | MR | Zbl

[12] J.A. Rodríguez-Velázquez and J.M. Sigarreta, Global defensive k -alliances in graphs. Discrete Appl. Math. 157 (2009) 211–218. | DOI | MR | Zbl

[13] K.H. Shafique, Partitioning a graph in alliances and its application to data clustering. Ph.D. thesis, University of Central Florida (2004).

[14] K.H. Shafique and R.D. Dutton, Maximum alliance-free and minimum alliance-cover sets. Congr. Numer. 162 (2003) 139–146. | MR | Zbl

[15] K.H. Shafique and R.D. Dutton, A tight bound on the cardinalities of maximun alliance-free and minimun alliance-cover sets. J. Combin. Math. Combin. Comput. 56 (2006) 139–145. | MR | Zbl

[16] K.H. Shafique and R.D. Dutton, On satisfactory partitioning of graphs. Congr. Numer. 154 (2002) 183–194. | MR | Zbl

[17] P. Turán, On an extremal problem in graph theory. Math. Fiz. Lapok. 48 (1941) 436–452. | JFM | MR | Zbl

[18] D.B. West, Introduction to Graph Theory, 2nd ed. Prentice Hall, USA (2001). | MR | Zbl

[19] I.G. Yero and J.A. Rodríguez-Velázquez, A survey on alliances in graphs: defensive alliances. Utilitas Math. 105 (2017) 141–172. | MR

[20] K. Zuse, Der Plankalkül (in German). Konrad Zuse Internet Archive (1972) 96–105. | MR

Cité par Sources :