Opuscula Mathematica
Opuscula Math. 42, no. 1 (2022), 31-54

γ-paired dominating graphs of cycles

Pannawat Eakawinrujee
Nantapath Trakultraipruk
Abstract. A paired dominating set of a graph \(G\) is a dominating set whose induced subgraph contains a perfect matching. The paired domination number, denoted by \(\gamma_{pr}(G)\), is the minimum cardinality of a paired dominating set of \(G\). A \(\gamma_{pr}(G)\)-set is a paired dominating set of cardinality \(\gamma_{pr}(G)\). The \(\gamma\)-paired dominating graph of \(G\), denoted by \(PD_{\gamma}(G)\), as the graph whose vertices are \(\gamma_{pr}(G)\)-sets. Two \(\gamma_{pr}(G)\)-sets \(D_1\) and \(D_2\) are adjacent in \(PD_{\gamma}(G)\) if there exists a vertex \(u\in D_1\) and a vertex \(v\notin D_1\) such that \(D_2=(D_1\setminus \{u\})\cup \{v\}\). In this paper, we present the \(\gamma\)-paired dominating graphs of cycles.
Keywords: paired dominating graph, paired dominating set, paired domination number.
Mathematics Subject Classification: 05C69, 05C38.
Full text (pdf)
References ▼
  1. [1] P. Eakawinrujee, N. Trakultraipruk, \(\gamma\)-paired dominating graphs of paths, Int. J. Math. Comput. Sci. 17 (2022), no. 2, 739-752.
  2. [2] G.H. Fricke, S.M. Hedetniemi, S.T. Hedetniemi, K.R. Hutson, \(\gamma\)-graphs of graphs, Discuss. Math. Graph Theory 31 (2011), 517-531.
  3. [3] R. Haas, K. Seyffarth, The \(k\)-dominating graph, Graphs Combin. 30 (2014), 609-617.
  4. [4] T.W. Haynes, P.J. Slater, Paired-domination in graphs, Networks 32 (1998), 199-206.
  5. [5] T.W. Haynes, S.T. Hedetniemi, P.J. Slater, Domination in Graphs: Advanced Topics, Marcel Dekker, New York, 1998.
  6. [6] T.W. Haynes, S.T. Hedetniemi, P.J. Slater, Fundamentals of Domination in Graphs, Marcel Dekker, New York, 1998.
  7. [7] S.A. Lakshmanan, A. Vijayakumar, The gamma graph of a graph, Graphs Combin. 7 (2010), 53-59.
  8. [8] R. Samanmoo, N. Trakultraipruk, N. Ananchuen, \(\gamma\)-independent dominating graphs of paths and cycles, Maejo Int. J. Sci. Technol. 13(03) (2019), 245-256.
  9. [9] D.B. West, Introduction to Graph Theory, Prentice Hall, Upper Saddle River, 2001.
  10. [10] A. Wongsriya, N. Trakultraipruk, \(\gamma\)-total dominating graphs of paths and cycles, ScienceAsia 43 (2017), 326-333.
About the authors ▼
Pannawat Eakawinrujee
https://orcid.org/0000-0003-1336-1019
Department of Mathematics and Statistics, Faculty of Science and Technology, Thammasat University, Pathum Thani 12120, Thailand
Nantapath Trakultraipruk (corresponding author)
https://orcid.org/0000-0002-2826-0176
Department of Mathematics and Statistics, Faculty of Science and Technology, Thammasat University, Pathum Thani 12120, Thailand
About the article ▼
Communicated by Dalibor Fronček.
Received: 2020-11-20.
Revised: 2021-08-30.
Accepted: 2021-12-01.
Published online: 2022-01-20.
Cite this article as ▼
Pannawat Eakawinrujee, Nantapath Trakultraipruk, γ-paired dominating graphs of cycles, Opuscula Math. 42, no. 1 (2022), 31-54, https://doi.org/10.7494/OpMath.2022.42.1.31.
Download this article's citation as: