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.
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://archive.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://archive.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://archive.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://archive.numdam.org/articles/10.1051/ro/2019049/
[1] and , Digraphs: Theory, Algorithms and Applications. Springer Monographs in Mathematics. Springer-Verlag, London Ltd., London (2007). | Zbl
[2] and , A survey on alliances and related parameters in graphs. Electron. J. Graph Theory Appl. 2 (2014) 70–86. | DOI | MR | Zbl
[3] , and , 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] , Dominating set and converse dominating set of a directed graph. Am. Math. Mon. 75 (1968) 861–863. | DOI | MR | Zbl
[5] and , Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman & Co., New York, USA (1979). | Zbl
[6] , and , Fundamentals of Domination in Graphs. Marcel Dekker, New York, NY (1998). | MR
[7] , Algorithms and complexity for alliances and weighted alliances of varoius types, Ph.D. thesis. Clemson University, Clemson, SC, USA (2007).
[8] , and , Alliances in graphs. J. Combin. Math. Combin. Comput. 48 (2004) 157–177. | MR | Zbl
[9] , and , Global offensive -alliances in digraphs. Preprint arXiv: [math.CO] (2019). | arXiv | MR
[10] , 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] , and , Alliances in graphs: parameters, properties and applications-A survey. AKCE Int. J. Graphs Comb. 15 (2018) 115–154. | DOI | MR | Zbl
[12] and , Global defensive -alliances in graphs. Discrete Appl. Math. 157 (2009) 211–218. | DOI | MR | Zbl
[13] , Partitioning a graph in alliances and its application to data clustering. Ph.D. thesis, University of Central Florida (2004).
[14] and , Maximum alliance-free and minimum alliance-cover sets. Congr. Numer. 162 (2003) 139–146. | MR | Zbl
[15] and , 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] and , On satisfactory partitioning of graphs. Congr. Numer. 154 (2002) 183–194. | MR | Zbl
[17] , On an extremal problem in graph theory. Math. Fiz. Lapok. 48 (1941) 436–452. | JFM | MR | Zbl
[18] , Introduction to Graph Theory, 2nd ed. Prentice Hall, USA (2001). | MR | Zbl
[19] and , A survey on alliances in graphs: defensive alliances. Utilitas Math. 105 (2017) 141–172. | MR
[20] , Der Plankalkül (in German). Konrad Zuse Internet Archive (1972) 96–105. | MR
Cité par Sources :
