Opuscula Math. 42, no. 1 (2022), 31-54
https://doi.org/10.7494/OpMath.2022.42.1.31
Opuscula Mathematica
γ-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.
- P. Eakawinrujee, N. Trakultraipruk, \(\gamma\)-paired dominating graphs of paths, Int. J. Math. Comput. Sci. 17 (2022), no. 2, 739-752.
- G.H. Fricke, S.M. Hedetniemi, S.T. Hedetniemi, K.R. Hutson, \(\gamma\)-graphs of graphs, Discuss. Math. Graph Theory 31 (2011), 517-531.
- R. Haas, K. Seyffarth, The \(k\)-dominating graph, Graphs Combin. 30 (2014), 609-617.
- T.W. Haynes, P.J. Slater, Paired-domination in graphs, Networks 32 (1998), 199-206.
- T.W. Haynes, S.T. Hedetniemi, P.J. Slater, Domination in Graphs: Advanced Topics, Marcel Dekker, New York, 1998.
- T.W. Haynes, S.T. Hedetniemi, P.J. Slater, Fundamentals of Domination in Graphs, Marcel Dekker, New York, 1998.
- S.A. Lakshmanan, A. Vijayakumar, The gamma graph of a graph, Graphs Combin. 7 (2010), 53-59.
- R. Samanmoo, N. Trakultraipruk, N. Ananchuen, \(\gamma\)-independent dominating graphs of paths and cycles, Maejo Int. J. Sci. Technol. 13(03) (2019), 245-256.
- D.B. West, Introduction to Graph Theory, Prentice Hall, Upper Saddle River, 2001.
- A. Wongsriya, N. Trakultraipruk, \(\gamma\)-total dominating graphs of paths and cycles, ScienceAsia 43 (2017), 326-333.
- 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
- Communicated by Dalibor Fronček.
- Received: 2020-11-20.
- Revised: 2021-08-30.
- Accepted: 2021-12-01.
- Published online: 2022-01-20.
