Geodesic
Connected coalitions in graphs
Discussiones Mathematicae. Graph Theory, Tome 44 (2024) no. 4, pp. 1551-1566 Cet article a éte moissonné depuis la source Library of Science

Voir la notice de l'article

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},
     year = {2024},
     volume = {44},
     number = {4},
     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
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
%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/

[1] S. Alikhani, D. Bakhshesh and H.R. Golmohammadi, Introduction to total coalitions in graphs. arXiv: 2211.11590

[2] S. Alikhani, H. Golmohammadi and E.V. Konstantinova, Coalition of cubic graphs of order at most 10, Commun. Comb. Optim. 9 (2024) 437–450. https://doi.org/10.22049/cco.2023.28328.1507

[3] S. Alikhani and S. Soltani, Distinguishing number and distinguishing index of natural and fractional powers of graphs, Bull. Iranian Math. Soc. 43 (2017) 2471–2482.

[4] D. Bakhshesh, M.A. Henning and D. Pradhan, On the coalition number of trees, Bull. Malays. Math. Sci. Soc. 46 (2023) 95. https://doi.org/10.1007/s40840-023-01492-4

[5] E.J. Cockayne and S.T. Hedetniemi, Towards a theory of domination in graphs, Networks 7 (1977) 247–261. https://doi.org/10.1002/net.3230070305

[6] D.-Z. Du and P.-J. Wan, Connected Dominating Set: Theory and Applications (Springer, New York, 2013). https://doi.org/10.1007/978-1-4614-5242-3

[7] B.L. Hartnell and D.F. Rall, Connected domatic number in planar graphs, Czechoslovak Math. J. 51 (2001) 173–179. https://doi.org/10.1023/A:1013770108453

[8] T.W. Haynes, J.T. Hedetniemi, S.T. Hedetniemi, A.A. McRae and R. Mohan, Introduction to coalitions in graphs, AKCE Int. J. Graphs Comb. 17 (2020) 653–659. https://doi.org/10.1080/09728600.2020.1832874

[9] T.W. Haynes, J.T. Hedetniemi, S.T. Hedetniemi, A.A. McRae and R. Mohan, Coalition graphs of paths, cycles and trees, Discuss. Math. Graph Theory 43 (2023) 931–946. https://doi.org/10.7151/dmgt.2416

[10] T.W. Haynes, J.T. Hedetniemi, S.T. Hedetniemi, A.A. McRae and R. Mohan, Upper bounds on the coalition number, Australas. J. Combin. 80 (2021) 442–453.

[11] T.W. Haynes, S.T. Hedetniemi and M.A.Henning, Topics in Domination in Graphs (Dev. Math. 64 Springer, Cham, 2020). https://doi.org/10.1007/978-3-030-51117-3

[12] T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Fundamentals of Domination in Graphs (Boca Ratan, CRC Press, New York, 1998). https://doi.org/10.1201/9781482246582

[13] T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Domination in Graphs, Advanced Topics (Routledge, Inc., New York, 1998). https://doi.org/10.1201/9781315141428

[14] E. Sampathkumar and H.B. Walikar, The connected domination number of a graph, J. Math. Phys. Sci. 13 (1979) 607–613.

[15] B. Zelinka, Domatic number and degrees of vertices of a graph, Math. Slovaca 33 (1983) 145–147.

[16] B. Zelinka, On domatic numbers of graphs, Math. Slovaca 31 (1981) 91–95.

[17] B. Zelinka, Connected domatic number of a graph, Math. Slovaca 36 (1986) 387–392.