Coalition of cubic graphs of order at most $10$

Document Type : Original paper

Authors

1 Department of Mathematical Sciences, Yazd University, 89195-741, Yazd, Iran

2 Novosibirsk State University, Pirogova str. 2, Novosibirsk, 630090, Russia

3 Sobolev Institute of Mathematics, Ak. Koptyug av. 4, Novosibirsk, 630090, Russia

Abstract

The coalition in a graph $G$ consists of two disjoint sets of vertices $V_{1}$ and $V_{2}$, neither of which is a dominating set but whose union $V_{1}\cup  V_{2}$, is a dominating set. A coalition partition in a graph $G$ is a vertex partition $\pi$ = $\{V_1, V_2,\dots, V_k \}$ such that every set $V_i \in \pi$ is not a dominating set but forms a coalition with another set $V_j\in \pi$ which is not a dominating set. The coalition number $C(G)$ equals the maximum $k$ of a coalition partition  of $G$. In this paper, we compute the coalition numbers of all cubic graphs of order at most $10$.

Keywords

Main Subjects

References

[1] S. Alikhani, D. Bakhshesh, and H.R. Golmohammadi, Total coalitions in graphs, Available at https://arxiv.org/abs/2211.11590.
[2] S. Alikhani and Y.H. Peng, Domination polynomials of cubic graphs of order 10, Turkish J. Math. 35 (2011), no. 3, 355–366.
https://doi.org/10.3906/mat-1002-141
[3] D. Bakhshesh, M.A. Henning, and D. Pradhan, On the coalition number of trees, Bull. Malaysian Math. Sci. Soc. 46 (2023), Article number: 95.
[4] E.J. Cockayne and S.T. Hedetniemi, Towards a theory of domination in graphs, Networks 7 (1977), no. 3, 247–261.
https://doi.org/10.1002/net.3230070305
[5] T.W. Haynes, J.T. Hedetniemi, S.T. Hedetniemi, A.A. McRae, and R. Mohan, Introduction to coalitions in graphs, AKCE Int. J. Graphs Combin. 17 (2020), no. 2, 653–659.
https://doi.org/10.1080/09728600.2020.1832874
[6] T.W. Haynes, J.T. Hedetniemi, S.T. Hedetniemi, A.A. McRae, and R. Mohan, Upper bounds on the coalition number, Austral. J. Combin. 80 (2021), no. 3, 442–453.
[7] T.W. Haynes, J.T. Hedetniemi, S.T. Hedetniemi, A.A. McRae, and R. Mohan, Coalition graphs, Commun. Comb. Optim. 8 (2023), no. 2, 423–430.
[8] 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), no. 4, 931–946.
https://doi.org/10.7151/dmgt.2416
[9] T.W. Haynes, S.T. Hedetniemi, and P.J. Slater, Domination in Graphs, Advanced Topics, Marcel Dekker, Inc., New York, 1998.
[10] T.W. Haynes, S.T. Hedetniemi, and P.J. Slater, Fundamentals of Domination in Graphs, Marcel Dekker, Inc. New York,
1998.
[11] G.B. Khosrovshahi, Ch. Maysoori, and B. Tayfeh-Rezaie, A note on 3-factorizations of $K_{10}$, J. Combin. Designs 9 (2001), no. 5, 379–383.
https://doi.org/10.1002/jcd.1018
[12] B. Zelinka, On domatic numbers of graphs, Math. Slovaca 31 (1981), no. 1, 91–95.
[13] B. Zelinka, Domatic number and degrees of vertices of a graph, Math. Slovaca 33 (1983), no. 2, 145–147.
[14] B. Zelinka, Domination in the generalized Petersen graphs, Czechoslov. Math. J. 52 (2002), no. 1, 11–16.
https://doi.org/10.1023/A:1021759001873
Communications in Combinatorics and Optimization
Volume 9, Issue 3
September 2024
Pages 437-450

Files

Share

How to cite

Statistics