γ-Paired dominating graphs of lollipop, umbrella and coconut graphs

Pannawat Eakawinrujee, Nantapath Trakultraipruk

Abstract


A paired dominating set of a graph G is a dominating set whose induced subgraph has a perfect matching. The paired domination number γpr(G) of G is the minimum cardinality of a paired dominating set. A paired dominating set D is a γpr(G)-set if |D|=γpr(G). The γ-paired dominating graph PDγ(G) of G is the graph whose vertex set is the set of all γpr(G)-sets, and two γpr(G)-sets D1 and D2 are adjacent in PDγ(G) if D2 = (D1 \ {u}) ∪ {v} for some u ∈ D1 and v ∉ D1. This paper determines the paired domination numbers of lollipop graphs, umbrella graphs, and coconut graphs. We also consider the γ-paired dominating graphs of those three graphs.


Keywords


paired dominating graph; paired domination number; gamma graph; lollipop graph; umbrella graph; coconut graph

Full Text:

PDF

DOI: http://dx.doi.org/10.5614/ejgta.2023.11.1.6

References

S. Alikhani, D. Fatehi, and C.M. Mynhardt, On k-total dominating graphs, Australas. J. Combin. 73 (2) (2019), 313–333.

Z.N. Berberler and M.E. Berberler, Independent strong domination in complementary prisms, Electron. J. Graph Theory Appl. 8 (1) (2020), 1–8. http://dx.doi.org/10.5614/ejgta.2020.8.1.1

A. Bień, Gamma graphs of some special classes of trees, Ann. Math. Sil. 29 (2015), 25–34. https://doi.org/10.1515/amsil-2015-0003

E. Connelly, S.T. Hedetniemi, and K.R. Hutson, A note on γ-graphs, AKCE Int. J. Graphs Comb. 8 (1) (2010), 23–31. https://doi.org/10.1080/09728600.2011.12088928

A. Das, Connected domination value in graphs, Electron. J. Graph Theory Appl. 9 (1) (2021), 113–123. http://dx.doi.org/10.5614/ejgta.2021.9.1.11

P. Eakawinrujee and N. Trakultraipruk, γ-paired dominating graphs of paths, Int. J. Math. Comput. Sci. 17 (2) (2022), 739–752.

P. Eakawinrujee and N. Trakultraipruk, γ-paired dominating graphs of cycles, Opuscula Math. 42 (1) (2022), 31–54. https://doi.org/10.7494/OpMath.2022.42.1.31

D. Fatehi, S. Alikhani, and A.J.M. Khalaf, The k-independent graph of a graph, Adv. Appl. Discrete Math. 18 (1) (2017), 45–56. http://dx.doi.org/10.17654/DM018010045

G.H. Fricke, S.M. Hedetniemi, S.T. Hedetniemi, and K.R. Hutson, γ-graphs of graphs, Discuss. Math. Graph Theory 31 (2011), 517–531.

R. Haas and K. Seyffarth, The k-dominating graph, Graphs Combin. 30 (2014), 609–617. https://doi.org/10.1007/s00373-013-1302-3

T.W. Haynes, S.T. Hedetniemi, and P.J. Slater, Fundamentals of Domination in Graphs, Marcel Dekker, New York, 1998.

T.W. Haynes, S.T. Hedetniemi, and P.J. Slater, Domination in Graphs: Advanced Topics, Marcel Dekker, New York, 1998.

T.W. Haynes and P.J. Slater, Paired-domination in graphs, Networks 32 (1998), 199–206.

F. Kazemnejad, B. Pahlavsay, E. Palezzato, and M. Torielli, Total domination number of middle graphs, Electron. J. Graph Theory Appl. 10 (1) (2022), 275–288. http://dx.doi.org/10.5614/ejgta.2022.10.1.19

S.A. Lakshmanan and A. Vijayakumar, The gamma graph of a graph, AKCE Int. J. Graphs Comb. 7 (2010), 53–59. https://doi.org/10.1080/09728600.2010.12088911

C.M. Mynhardt and L.E. Teshima, A note on some variations of the γ-graph, J. Combin. Math. Combin. Comput. 104 (2018), 217–230.

C.M. Mynhardt and A. Roux, Irredundance graphs, Discrete Appl. Math. 322 (2022), 36–48. https://doi.org/10.1016/j.dam.2022.08.005

C.M. Mynhardt, A. Roux, and L.E. Teshima, Connected k-dominating graphs, Discrete Math. 342 (2019), 145–151. https://doi.org/10.1016/j.disc.2018.09.006

R. Samanmoo, N. Trakultraipruk, and N. Ananchuen, γ-independent dominating graphs of paths and cycles, Maejo Int. J. Sci. Technol. 13 (03) (2019), 245–256.

S. Sanguanpong and N. Trakultraipruk, γ-induced-paired dominating graphs of paths and cycles, Discrete Math. Algorithms Appl. 14 (08) (2022), 2250047. https://doi.org/10.1142/S1793830922500471

K. Subramanian and N. Sridharan, γ-graph of a graph, Bull. Kerala Math. Assoc. 5(1) (2008), 17–34.

D.B. West, Introduction to Graph Theory (Second Edition), Prentice-Hall, Inc., Upper Saddle River, 2001.

A. Wongsriya and N. Trakultraipruk, γ-Total dominating graphs of paths and cycles, ScienceAsia 43 (2017), 326–333. https://doi.org/10.2306/scienceasia1513-1874.2017.43.326


Refbacks

  • There are currently no refbacks.


ISSN: 2338-2287

Creative Commons License
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.

View EJGTA Stats