γ-Total Dominating Graphs of Lollipop, Umbrella, and Coconut Graphs

Document Type : Original paper

Authors

Department of Mathematics and Statistics, Faculty of Science and Technology, Thammasat University, Pathum Thani 12120, Thailand

Abstract

A total dominating set of a graph G is a set DV(G) such that every vertex of G is adjacent to some vertex in D. The total domination number γt(G) of G is the minimum cardinality of a total dominating set. The γ-total dominating graph TDγ(G) of G is the graph whose vertices are minimum total dominating sets, and two minimum total dominating sets of TDγ(G) are adjacent if they differ by only one vertex. In this paper, we determine the total domination numbers of lollipop graphs, umbrella graphs, and coconut graphs, and especially their γ-total dominating graphs.

Keywords

Main Subjects


[1] S. Alikhani, D. Fatehi, and C.M. Mynhardt, On k-total dominating graphs, Australas. J. Combin. 73 (2019), no. 2, 313––333.
[2] A. Bień, Gamma graphs of some special classes of trees, Ann. Math. Sil. 29 (2015), no. 1, 25––34.
https://doi.org/10.1515/amsil-2015-0003
[3] E.J. Cockayne, R.M. Dawes, and S.T. Hedetniemi, Total domination in graphs, Networks 10 (1998), no. 3, 211–219.
https://doi.org/10.1002/net.3230100304
[4] E. Connelly, K.R. Hutson, S.T. Hedetniemi, and T.W. Haynes, A note on γ-graphs, AKCE Int. J. Graphs Comb. 8 (2011), no. 1, 23–31.
[5] P. Eakawinrujee and N. Trakultraipruk, γ-paired dominating graphs of cycles, Opusc. Math. 42 (2022), no. 1, 31–54.
https://doi.org/10.7494/OpMath.2022.42.1.31
[6] P. Eakawinrujee and N. Trakultraipruk, γ-paired dominating graphs of paths, Int. J. Math. Comput. Sci. 17 (2022), no. 2, 739–752.
[7] P. Eakawinrujee and N. Trakultraipruk, γ-paired dominating graphs of lollipop, umbrella and coconut graphs, Electron. J. Graph Theory Appl. 11 (2023), no. 1, 65–79.
http://dx.doi.org/10.5614/ejgta.2023.11.1.6
[8] D. Fatehi, S. Alikhani, and A.J.M. Khalaf, The k-independent graph of a graph, Adv. Appl. Discrete Math. 18 (2017), no. 1, 45–56.
http://dx.doi.org/10.17654/DM018010045
[9] G. Fricke, S. Hedetniemi, S. Hedetniemi, and K. Hutson, γ-graphs of graphs, Discuss. Math. Graph Theory 31 (2011), no. 3, 517–531.
https://doi.org/10.7151/dmgt.1562
[10] R. Haas and K. Seyffarth, The k-dominating graph, Graphs Combin. 30 (2014), 609–617.
https://doi.org/10.1007/s00373-013-1302-3
[11] R. Haas and K. Seyffarth, Reconfiguring dominating sets in some well-covered and other classes of graphs, Discrete Math. 340 (2017), no. 8, 1802–1817.
https://doi.org/10.1016/j.disc.2017.03.007
[12] T.W. Haynes, S.T. Hedetniemi, and P.J. Slater, Domination in Graphs: Advanced Topics, Marcel Dekker, New York, 1998.
[13] T.W. Haynes, S.T. Hedetniemi, and P.J. Slater, Fundamentals of Domination in Graphs, Marcel Dekker, New York,
1998.
[14] M.A. Henning, Graphs with large total domination number, J. Graph Theory 35 (2000), no. 1, 21–45.
[15] S.A. Lakshmanan, A. Vijayakumar, and S. Arumugam, The gamma graph of a graph, AKCE Int. J. Graphs Comb. 7 (2010), no. 1, 53–59.
[16] C.M. Mynhardt, A. Roux, and L.E. Teshima, Connected k-dominating graphs, Discrete Math. 342 (2019), no. 1, 145–151.
https://doi.org/10.1016/j.disc.2018.09.006
[17] C.M. Mynhardt and L.E. Teshima, A note on some variations of the γ-graph, J. Comb. Math. Comb. Comput. 104 (2018), 217—-230.
[18] R. Samanmoo, N. Trakultraipruk, and N. Ananchuen, γ-independent dominating graphs of paths and cycles, Maejo Int. J. Sci. Technol. 13 (2019), no. 3, 245–256.
[19] S. Sanguanpong and N. Trakultraipruk, γ-induced-paired dominating graphs of paths and cycles, Discrete Math. Algorithms Appl. 14 (2022), no. 8, Article ID: 2250047.
https://doi.org/10.1142/S1793830922500471