Results of Paired Domination of Some Special Graph Families on Transformation Graphs: $G^{xy+}$ and $G^{xy-}$

Abstract

In this study, transformation graphs obtained from the concept of the total graph and the result of its paired domination number for some special graph families are discussed. If a subset $S$ of the vertex set of the graph $G$ dominates and the induced subgraph $⟨S⟩$ has a perfect matching that covers every vertex of the graph, then $S$ is called a paired-dominating set of $G$. A paired dominating set with the smallest cardinality is denoted by $\gamma_{pr}$-set. Haynes and Slater introduced paired domination parameters. The present study commences with assessing outcomes stemming from eight permutations within the realm of path graphs. Subsequently, building upon this foundational structure, the results are extrapolated from the realm of cycle transformation graph structures based on findings from path transformation graphs.

Keywords

• Graph theory
• graph vulnerability
• paired domination number
• transformation graphs

References

1. E. J. Cockayne, R. M. Dawes, S. T. Hedetniemi, Total Domination in Graphs, Networks 10 (3) (1980) 211-219.
2. T. W. Haynes, P. J. Slater, Paired-Domination in Graphs, Networks 32 (3) (1998) 199-206.
3. W. J. Desormeaux, M. A. Henning, Paired Domination in Graphs: A Survey and Recent Results, Utilitas Mathematica 94 (2014) 101–166.
4. M. Chellali, T. W. Haynes, Total and Paired-Domination Numbers of a Tree, AKCE International Journal of Graphs and Combinatorics 1 (2) (2004) 69–75.
5. A. D. Gray, M. A. Henning, Paired-Domination Game Played on Cycles, Discrete Applied Mathematics 336 (2023) 132–140.
6. P. Eakawinrujee, N. Trakultraipruk, Total and Paired Domination Numbers of Windmill Graphs, Asian-European Journal of Mathematics 16 (7) (2023) 2350123.
7. P. Dorbec, S. Gravier, M. A. Henning, Paired-Domination in Generalized Claw-Free Graphs, Journal of Combinatorial Optimization 14 (2007) 1–7.
8. T. W. Haynes, P. J. Slater, Paired-Domination and the Paired-Domatic Number, Congressus Numerantium 109 (1995) 65–72.

9. S. Fitzpatrick, B. Hartnel, Paired-Domination, Discussiones Mathematicae Graph Theory 18 (1998) 63¬–72.
10. B. Bresar, M. A. Henning, D. F. Rall, Paired-Domination of Cartesian Products of Graphs, Utilitas Mathematica 22 (1) (2005) 233–237.
11. M. Dettlaff, D. Gözüpek, J. Raczek, Paired Domination Versus Domination and Packing Number in Graphs, Journal of Combinatorial Optimization 44 (2022) 921–933.
12. T. W. Haynes, S. T. Hedetniemi, M. A. Henning, Domination in Graphs: Core Concepts, Springer, Cham, 2022.
13. T. W. Haynes, S. T. Hedetniemi, M. A. Henning, Topics in Domination in Graphs, Springer, Cham, 2020.
14. T. W. Haynes, S. T. Hedetniemi, M. A. Henning, Structures of Domination in Graphs, Springer, Cham, 2021.
15. G. Chartrand, L. Lesniak, P. Zhang, Graphs & Digraphs, 6th Edition, Chapman and Hall/CRC, New York, 2015.
16. M. Behzad, A Criterion for the Planarity of a Total Graph, Mathematical Proceedings of Cambridge Philosophy Society 63 (1967) 679–681.
17. B. Wu, J. Meng, Basic Properties of Total Transformation Graphs, Journal of Mathematical Study 34 (2) (2001) 109–116.
18. J. W. Moon, On the Line-Graph of the Complete Bigraph, The Annals of Mathematical Statistics 34 (1963) 664–667.
19. V. Aytac, T. Turaci, Analysis of Vulnerability of Some Transformation Networks, International Journal of Foundations of Computer Science 34 (1) (2023) 11–24.
20. A. Aytac, T. Turaci, Vulnerability Measures of Transformation Graph G^(xy+), International Journal of Foundations of Computer Science 26 (6) (2015) 667–675.
21. A. Aytac, T. Turaci, Bondage and Strong-Weak Bondage Numbers of Transformation Graphs G^xyz, International Journal of Pure and Applied Mathematics 106 (2) (2016) 689–698.
22. A. Aytac, T. Turaci, On the Domination, Strong and Weak Domination in Transformation Graph G^(xy-), Utilitas Mathematica 113 (2019) 181–189.
23. M. K. A. Jebitha, J. P. Joseph, Domination in Transformation Graph, International Journal of Mathematical Combinatorics 1 (2012) 58–73.
24. X. Lan, W. Baoyindureng, Transformation Graph, Discrete Mathematics 308 (2008) 5144–5148.
25. L. Yi, B. Wu, The Transformation Graph G^(++-), The Australasian Journal of Combinatorics 44 (2009) 37–42.
26. W. Baoyindureng, L. Zhang, Z. Zhang, The Transformation Graph G^xyz when xyz=-++, Discrete Mathematics 296 (2005) 263–270.