Coalition graphs of connected domination partitions in subcubic graphs

Articles in Press

Document Type : Special issue of CCO to honor Odile Favaron

Authors

Sobolev Institute of Mathematics, Siberian Branch of the Russian Academy of Sciences, Novosibirsk, 630090, Russia

Abstract

A graph is subcubic if it is connected and its maximum vertex degree does not exceed 3. Two disjoint vertex subsets of a graph $G$ form a connected coalition in $G$ if neither of them is a connected dominating set but their union is a connected dominating set. A connected coalition partition of $G$ is a partition of its vertices $\pi(G) = \{V_1, V_2,..., V_k \}$, such that each $V_i$ is either a connected dominating set consisting of a single vertex or forms a coalition with some set of $\pi(G)$. The formation of connected coalitions is described by a coalition graph whose vertices correspond to the sets of $\pi$, and two vertices are adjacent if and only if the corresponding sets form a coalition in $G$. We characterize all coalition graphs of subcubic graphs.

Keywords

Main Subjects

References

[1] S. Alikhani, D. Bakhshesh, H.R. Golmohammadi, and E.V. Konstantinova, Connected coalitions in graphs, Discuss. Math. Graph Theory 44 (2024), no. 4, 1551–1566. https://doi.org/10.7151/dmgt.2509
[2] S. Alikhani, H.R. Golmohammadi, and E.V. Konstantinova, Coalition of cubic graphs of order at most 10, Commun. Comb. Optim. 9 (2024), no. 3, 437–450. https://doi.org/10.22049/cco.2023.28328.1507
[3] D. Bakhshesh, M.A. Henning, and D. Pradhan, On the coalition number of trees, Bull. Malays. Math. Sci. Soc. 46 (2023), no. Article ID: 95. https://doi.org/10.1007/s40840023014924
[4] A.A Dobrynin and H. Golmohammadi, On cubic graphs having the maximum coalition number, Sib. `Elektron. Math. Izv. 21 (2024), no. 1, 363–369. https://doi.org/10.33048/semi.2024.21.027
[5] A.A. Dobrynin and H. Golmohammadi, The shortest cycle having the maximal number of coalition graphs, Discrete Math. Lett. 14 (2024), 21–26. https://doi.org/10.47443/dml.2024.111
[6] D.Z. Du and P.J. Wan, Connected dominating set: Theory and applications, 2013.
[7] W. Duckworth and B. Mans, Connected domination of regular graphs, Discrete Math. 309 (2009), no. 8, 2305–2322.
https://doi.org/10.1016/j.disc.2008.05.029
[8] A.N. Glebov and A.A Dobrynin, Universal cycles that generate all graphs of coalition partitions in cycles, J. Appl. Ind. Math. 19 (2025), no. 1, 33–39. https://doi.org/10.1134/S199047892501003X
[9] X. Guan and M. Wang, On the connected coalition number, J. Combin. Math. Combin. Comput. 127 (2025), 219–230.
https://doi.org/10.61091/jcmcc127-16
[10] 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), no. 2, 653–659. https://doi.org/10.1080/09728600.2020.1832874
[11] 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), no. 3, 442–453.
[12] T.W. Haynes, J.T. Hedetniemi, S.T. Hedetniemi, A.A. McRae, and R. Mohan, Coalition graphs, Commun. Combin. Optim. 8 (2023), no. 2, 423–430. https://doi.org/10.22049/CCO.2022.27916.1394
[13] 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
[14] T.W. Haynes, J.T. Hedetniemi, S.T. Hedetniemi, A.A. McRae, and R. Mohan, Self-coalition graphs, Opuscula Math. 43 (2023), no. 2, 173–183. https://doi.org/10.7494/opmath.2023.43.2.173
[15] T.W. Haynes, S.T. Hedetniemi, and M.A. Henning, Topics in domination in graphs, Developments in Mathematics, Springer Cham, 2020.
[16] T.W. Haynes, S.T. Hedetniemi, and M.A. Henning, Structures of domination in graphs, Springer Cham, 2021.
[17] T.W. Haynes, S.T. Hedetniemi, and M.A. Henning, Domination in graphs: Core concepts, Springer Cham, 2023.
[18] T.W. Haynes, S.T. Hedetniemi, and P.J. Slater, Fundamentals of domination in graphs, Chapman and Hall/CRC Pure and Applied Mathematics Series, Marcel Dekker Inc., New York, 1998.
[19] S.T. Hedetniemi and R. Laskar, Connected domination in graphs, Graph Theory and Combinatorics (1984), 209–218.
[20] E. Sampathkumar and H.B. Walikar, The connected domination number of a graph, J. Math. Phys. Sci. 13 (1979), no. 6, 607–613.
[21] F. Wang, D.Z. Du, and X. Cheng, Connected dominating set, Springer, New York, 2016.
Communications in Combinatorics and Optimization

Articles in Press, Accepted Manuscript
Available Online from 25 April 2026

Files

Share

How to cite

Statistics