Total coalitions of cubic graphs of order at most 10

Document Type : Original paper

Author

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

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

Abstract

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

Keywords

Main Subjects

References

[1] S. Alikhani, D. Bakhshesh, and H. Golmohammadi, Total coalitions in graphs, (submitted).
[2] S. Alikhani, D. Bakhshesh, H. Golmohammadi, and E.V. Konstantinova, Connected coalitions in graphs, Discuss. Math. Graph Theory, In press.
https://doi.org/10.7151/dmgt.2509
[3] S. Alikhani, H. Golmohammadi, and E. Konstantinova, Coalition of cubic graphs of order at most 10, Commun. Comb. Optim., In press.
https://doi.org/10.22049/cco.2023.28328.1507
[4] 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
[5] J. Bar´at and Z.L. Bl´azsik, General sharp upper bounds on the total coalition number, Discuss. Math. Graph Theory, In press.
https://doi.org/10.7151/dmgt.2511
[6] E.J. Cockayne, R.M. Dawes, and S.T. Hedetniemi, Total domination in graphs, Networks 10 (1980), no. 3, 211–219.
https://doi.org/10.1002/net.3230100304
[7] 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
[8] J. Cyman, M. Dettlaff, M.A. Henning, M. Lema´nska, and J. Raczek, Total domination versus domination in cubic graphs, Graphs Combin. 34 (2018), no. 1, 261–276.
https://doi.org/10.1007/s00373-017-1865-5
[9] W.J. Desormeaux, T.W. Haynes, and M.A. Henning, Partitioning the vertices of a cubic graph into two total dominating sets, Discrete Appl. Math. 223 (2017), 52–63.
https://doi.org/10.1016/j.dam.2017.01.032
[10] T.W. Haynes, J.T. Hedetniemi, S.T. Hedetniemi, A. McRae, and R. Mohan, Coalition graphs, Commun. Comb. Optim. 8 (2023), no. 2, 423–430.
https://doi.org/10.22049/cco.2022.27916.1394
[11] 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
[12] 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.
[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), no. 4, 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.
http://dx.doi.org/10.7494/OpMath.2023.43.2.173.
[15] T.W. Haynes, S. Hedetniemi, and P. Slater, Fundamentals of Domination in Graphs, CRC press, 2013.
[16] T.W. Haynes, S.T. Hedetniemi, and M.A. Henning, Domination in Graphs: Core Concepts, Springer, 2023.
[17] M.A. Henning and A. Yeo, Total Domination in Graphs, Springer, 2013.
[18] J. Southey and M.A. Henning, Dominating and total dominating partitions in cubic graphs, Cent. Eur. J. Math. 9 (2011), no. 3, 699–708.
https://doi.org/10.2478/s11533-011-0014-2
[19] B. Zelinka, On domatic numbers of graphs, Math. Slovaca 31 (1981), no. 1, 91–95.
[20] B. Zelinka, Domatic number and degrees of vertices of a graph, Math. Slovaca 33 (1983), no. 2, 145–147.
[21] B. Zelinka, Total domatic number and degrees of vertices of a graph, Math. Slovaca 39 (1989), no. 1, 7–11.
Communications in Combinatorics and Optimization

Articles in Press, Accepted Manuscript
Available Online from 30 January 2024

Files

Share

How to cite

Statistics