Geodesic
On cubic graphs having the maximum coalition number
Sibirskie èlektronnye matematičeskie izvestiâ, Tome 21 (2024) no. 1, pp. 363-369 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

A coalition in a graph $G$ with a vertex set $V$ consists of two disjoint sets $V_1, V_2\subset V$, such that neither $V_1$ nor $V_2$ is a dominating set, but the union $V_1\cup V_2$ is a dominating set in $G$. A partition of graph vertices is called a coalition partition $\mathcal{P}$ if every non-dominating set of $\mathcal{P}$ is a member of a coalition, and every dominating set is a single-vertex set. The coalition number $C(G)$ of a graph $G$ is the maximum cardinality of its coalition partitions. It is known that for cubic graphs $C(G) \le 9$. The existence of cubic graphs with the maximum coalition number is an unsolved problem. In this paper, an infinite family of cubic graphs satisfying $C(G)=9$ is constructed.
Keywords: dominating set, coalition number, cubic graph. 
@article{SEMR_2024_21_1_a19,
     author = {A. A. Dobrynin and H. Golmohammadi},
     title = {On cubic graphs having the maximum coalition number},
     journal = {Sibirskie \`elektronnye matemati\v{c}eskie izvesti\^a},
     pages = {363--369},
     year = {2024},
     volume = {21},
     number = {1},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/SEMR_2024_21_1_a19/}
}
TY  - JOUR
AU  - A. A. Dobrynin
AU  - H. Golmohammadi
TI  - On cubic graphs having the maximum coalition number
JO  - Sibirskie èlektronnye matematičeskie izvestiâ
PY  - 2024
SP  - 363
EP  - 369
VL  - 21
IS  - 1
UR  - http://geodesic.mathdoc.fr/item/SEMR_2024_21_1_a19/
LA  - en
ID  - SEMR_2024_21_1_a19
ER  - 
%0 Journal Article
%A A. A. Dobrynin
%A H. Golmohammadi
%T On cubic graphs having the maximum coalition number
%J Sibirskie èlektronnye matematičeskie izvestiâ
%D 2024
%P 363-369
%V 21
%N 1
%U http://geodesic.mathdoc.fr/item/SEMR_2024_21_1_a19/
%G en
%F SEMR_2024_21_1_a19
A. A. Dobrynin; H. Golmohammadi. On cubic graphs having the maximum coalition number. Sibirskie èlektronnye matematičeskie izvestiâ, Tome 21 (2024) no. 1, pp. 363-369. http://geodesic.mathdoc.fr/item/SEMR_2024_21_1_a19/

[1] S. Alikhani, H. Golmohammadi, E. Konstantinova, “Coalition of cubic graphs of order at most 10”, Commun. Comb. Optim., 2023 | DOI | MR

[2] S. Alikhani, D. Bakhshesh, H. Golmohammadi, Introduction to total coalitions in graphs, 2022, arXiv: 2211.11590 | MR

[3] S. Alikhani, D. Bakhshesh, H. Golmohammadi, S. Klavzar, “On independent coalition in graphs and independent coalition graphs”, Discuss. Math. Graph Theory, 2024 | DOI | MR

[4] S. Alikhani, D. Bakhshesh, H.R. Golmohammadi, E.V. Konstantinova, “Connected coalitions in graphs”, Discuss. Math. Graph Theory, 2023 | DOI | MR

[5] D. Bakhshesh, M. A. Henning, D. Pradhan, “On the coalition number of trees”, Bull. Malays. Math. Sci. Soc. (2), 46:3 (2023), 95 | DOI | MR | Zbl

[6] A. Cabrera-Martínez, J.A. Rodríguez-Velázquez, “A note on double domination in graphs”, Discrete Appl. Math., 300 (2021), 107–111 | DOI | MR | Zbl

[7] W.J. Desormeaux, T.W. Haynes, M.A. Henning, “Bounds on the connected domination number of a graph”, Discrete Appl. Math., 161:18 (2013), 2925–2931 | DOI | MR | Zbl

[8] W. Goddard, M.A. Henning, “Independent domination in graphs: A survey and recent results”, Discrete Math., 313:7 (2013), 839–854 | DOI | MR | Zbl

[9] H. Golmohammadi, “Total coalitions of cubic graphs of at most order 10”, Commun. Comb. Optim., 2024 | DOI | MR

[10] F. Harary, T.W. Haynes, “Double domination in graphs”, Ars Comb., 55 (2000), 201–213 | MR | Zbl

[11] T.W. Haynes, J.T. Hedetniemi, S.T. Hedetniemi, A.A. McRae, R. Mohan, “Introduction to coalitions in graphs”, AKCE Int. J. Graphs Combin., 17:2 (2020), 653–659 | DOI | MR | Zbl

[12] T.W. Haynes, J.T. Hedetniemi, S.T. Hedetniemi, A.A. McRae, R. Mohan, “Coalition graphs of paths, cycles, and trees”, Discuss. Math. Graph Theory, 43:4 (2023), 931–946 | DOI | MR

[13] T.W. Haynes, J.T. Hedetniemi, S.T. Hedetniemi, A.A. McRae, R. Mohan, “Upper bounds on the coalition number”, Austral. J. Combin., 80:3 (2021), 442–453 | MR | Zbl

[14] T.W. Haynes, J.T. Hedetniemi, S.T. Hedetniemi, A.A. McRae, R. Mohan, “Coalition graphs”, Commun. Comb. Optim., 8:2 (2023), 423–430 | DOI | MR | Zbl

[15] T.W. Haynes, S.T. Hedetniemi, M.A. Henning, Domination in graphs: core concepts, Springer Monographs in Mathematics, Springer, Cham, 2023 | DOI | MR | Zbl

[16] T.W. Haynes, S.T. Hedetniemi, P.J. Slater, Fundamentals of domination in graphs, Pure and Applied Mathematics, 208, Marcel Dekker Inc., New York, 1998 | DOI | MR | Zbl

[17] M.A. Henning, A. Yeo, Total domination in graphs, Springer Monographs in Mathematics, Springer, New York, 2013 | DOI | MR | Zbl