Reconfiguring Minimum Independent Dominating Sets in Graphs

Document Type : Original paper

Authors

1 Department of Mathematics and Statistics, Thompson Rivers University, 805 TRU Way, Kamloops, B.C., Canada

2 Department of Mathematics and Statistics, University of Victoria, PO BOX 1700 STN CSC, Victoria, B.C. Canada

Abstract

The independent domination number $i(G)$ of a graph $G$ is the minimum cardinality of a maximal independent set of $G$, also called an $i(G)$-set. The $i$-graph of $G$, denoted $\mathscr{I}(G)$, is the graph whose vertices correspond to the $i(G)$-sets, and where two $i(G)$-sets are adjacent if and only if they differ by two adjacent vertices. We show that not all graphs are $i$-graph realizable, that is, given a target graph $H$, there does not necessarily exist a seed graph $G$ such that $H \cong \mathscr{I}(G)$.  Examples of such graphs include $K_{4}-e$ and $K_{2,3}$. We build a series of tools to show that known $i$-graphs can be used to construct new $i$-graphs and apply these results to build other classes of $i$-graphs, such as block graphs, hypercubes, forests, cacti, and unicyclic graphs.

Keywords

Main Subjects

References

[1] K. Adaricheva, C. Bozeman, N.E. Clarke, R. Haas, M.-E. Messinger, K. Seyffarth, and H.C. Smith, Reconfiguration graphs for dominating sets, Research Trends in Graph Theory and Applications (Cham) (D. Ferrero, L. Hogben, S.R. Kingan, and G.L. Matthews, eds.), Springer International Publishing, 2021, pp. 119–135.
[2] S. Alikhani, D. Fatehi, and S. Klavˇzar, On the structure of dominating graphs, Graphs Combin. 33 (2017), no. 4, 665–672.
https://doi.org/10.1007/s00373-017-1792-5
[3] A. Bień, Gamma graphs of some special classes of trees, Ann. Math. Sil. 29 (2015), 25–34.
[4] J.A. Bondy, The “graph theory” of the Greek alphabet, Graph theory and applications (Proc. Conf., Western Michigan Univ., Kalamazoo, Mich., 1972; dedicated to the memory of J. W. T. Youngs), Lecture Notes in Math., Vol. 303, Springer,
Berlin, 1972, pp. 43–54. 
[5] R.C. Brewster, C.M. Mynhardt, and L.E. Teshima, The i-graphs of paths and cycles, In Preparation (2023).
[6] R.C. Brewster, C.M. Mynhardt, and L.E. Teshima, The realizability of theta graphs as $i$-graphs, In Preparation (2023).
[7] G. Chartrand, L. Lesniak, and P. Zhang, Graphs and Digraphs, 6th ed., Chapman & Hall, London, 2015.
[8] E. Connelly, K.R. Hutson, and S.T. Hedetniemi, A note on $\gamma$-graphs, AKCE Int. J. Graphs Comb. 8 (2011), no. 1, 23–31.
[9] Michelle Edwards, Vertex-critically and bicritically for independent domination and total domination in graphs, Ph.D. thesis, University of Victoria, 2015.
[10] G.H. Fricke, S.M. Hedetniemi, S.T. Hedetniemi, and K.R. Hutson, $\gamma$-graphs of graphs, Discuss. Math. Graph Theory 31 (2011), no. 3, 517–531.
[11] R. Haas and K. Seyffarth, The $k$-dominating graph, Graphs Combin. 30 (2014), no. 3, 609–617.
https://doi.org/10.1007/s00373-013-1302-3
[12] 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
[13] A. Haddadan, T. Ito, A.E. Mouawad, N. Nishimura, H. Ono, A. Suzuki, and Y. Tebbal, The complexity of dominating set reconfiguration, Theoret. Comput. Sci. 651 (2016), 37–49.
https://doi.org/10.1016/j.tcs.2016.08.016
[14] T.W. Haynes, S.T. Hedetniemi, and P.J. Slater, Domination in Graphs: Advance Topics, Marcel Dekker, New York, 1998.
[15] T.W. Haynes, S.T. Hedetniemi, and P.J. Slater, Fundamentals of Domination in Graphs, Marcel Dekker, New York,
1998.
[16] T. Ito, E.D. Demaine, N.J.A. Harvey, C.H. Papadimitriou, M. Sideri, R. Uehara, and Y. Uno, On the complexity of reconfiguration problems, Theoret. Comput. Sci. 412 (2011), no. 12-14, 1054–1065.
https://doi.org/10.1016/j.tcs.2010.12.005
[17] S.A. Lakshmanan and A. Vijayakumar, The gamma graph of a graph, AKCE Int. J. Graphs Comb. 7 (2010), no. 1, 53–59.
[18] C.M. Mynhardt and S. Nasserasr, Reconfiguration of colourings and dominating sets in graphs, 50 years of combinatorics, graph theory, and computing, Discrete Math. Appl. (Boca Raton), CRC Press, Boca Raton, FL, 2020, pp. 171–191. 
[19] C.M. Mynhardt and L. E. Teshima, A note on some variations of the $\gamma$-graph, J. Combin. Math. Combin. Comput. 104 (2018), 217–230.
[20] N. Nishimura, Introduction to reconfiguration, Algorithms 11 (2018), no. 4, Article ID: 52.
https://doi.org/10.3390/a11040052
[21] N. Sridharan, S. Amutha, and S.B. Rao, Induced subgraphs of gamma graphs, Discrete Math. Algorithms Appl. 5 (2013), no. 3, Article ID: 1350012.
https://doi.org/10.1142/S1793830913500122
[22] N. Sridharan and K. Subramanian, Trees and unicyclic graphs are γ-graphs, J. Combin. Math. Combin. Comput. 69 (2009), 231–236.
[23] K. Subramanian and N. Sridharan, $\gamma$-graph of a graph, Bull. Kerala Math. Assoc. 5 (2008), no. 1, 17–34.
[24] A. Suzuki, A.E. Mouawad, and N. Nishimura, Reconfiguration of dominating sets, J. Comb. Optim. 32 (2016), no. 4, 1182–1195.
https://doi.org/10.1007/s10878-015-9947-x
[25] L.E. Teshima, The $i$-graph and other variations on the γ-graph, Ph.D. thesis, University of Victoria, 2022, https://dspace.library.uvic.ca/handle/1828/14602
Communications in Combinatorics and Optimization
Volume 9, Issue 3
September 2024
Pages 389-411

Files

Share

How to cite

Statistics