Geodesic
Connected coalitions in graphs
Discussiones Mathematicae. Graph Theory, Tome 44 (2024) no. 4, pp. 1551-1566

Voir la notice de l'article provenant de la source Library of Science

Let G = (V,E) be a graph, and define a connected coalition as a pair of disjoint vertex sets U_1 and U_2 such that U_1∪ U_2 forms a connected dominating set, but neither U_1 nor U_2 individually forms a connected dominating set. A connected coalition partition of G is a partition Φ={U_1, U_2,..., U_k} of the vertices such that each set U_i ∈Φ either consists of only a single vertex with degree n-1, or forms a connected coalition with another set U_j∈Φ that is not a connected dominating set. The connected coalition number C C(G) is defined as the largest possible size of a connected coalition partition for G. The objective of this study is to initiate an examination into the notion of connected coalitions in graphs and present essential findings. More precisely, we provide a thorough characterization of all graphs possessing a connected coalition partition. Moreover, we establish that, for any graph G with order n, a minimum degree of 1, and no full vertex, the condition C C(G) lt;n holds. In addition, we prove that any tree T achieves C C(T)=2. Lastly, we propose two polynomial-time algorithms that determine whether a given connected graph G of order n satisfies C C(G)=n or C C(G)=n-1.
Keywords: coalition, coalition partition, polynomial-time algorithm, corona product 
@article{DMGT_2024_44_4_a16,
     author = {Alikhani, Saeid and Bakhshesh, Davood and Golmohammadi, Hamidreza and Konstantinova, Elena V.},
     title = {Connected coalitions in graphs},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {1551--1566},
     publisher = {mathdoc},
     volume = {44},
     number = {4},
     year = {2024},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2024_44_4_a16/}
}
TY  - JOUR
AU  - Alikhani, Saeid
AU  - Bakhshesh, Davood
AU  - Golmohammadi, Hamidreza
AU  - Konstantinova, Elena V.
TI  - Connected coalitions in graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2024
SP  - 1551
EP  - 1566
VL  - 44
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2024_44_4_a16/
LA  - en
ID  - DMGT_2024_44_4_a16
ER  - 
%0 Journal Article
%A Alikhani, Saeid
%A Bakhshesh, Davood
%A Golmohammadi, Hamidreza
%A Konstantinova, Elena V.
%T Connected coalitions in graphs
%J Discussiones Mathematicae. Graph Theory
%D 2024
%P 1551-1566
%V 44
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2024_44_4_a16/
%G en
%F DMGT_2024_44_4_a16
Alikhani, Saeid; Bakhshesh, Davood; Golmohammadi, Hamidreza; Konstantinova, Elena V. Connected coalitions in graphs. Discussiones Mathematicae. Graph Theory, Tome 44 (2024) no. 4, pp. 1551-1566. http://geodesic.mathdoc.fr/item/DMGT_2024_44_4_a16/