Reconfiguring Minimum Independent Dominating Sets in Graphs

Brewster, Richard C; Mynhardt, Christina M; Teshima, Laura E

doi:10.22049/cco.2023.28965.1797

تعداد نشریات	7
تعداد شماره‌ها	102
تعداد مقالات	1,145
تعداد مشاهده مقاله	1,053,888
تعداد دریافت فایل اصل مقاله	876,769

	Reconfiguring Minimum Independent Dominating Sets in Graphs
Communications in Combinatorics and Optimization
مقالات آماده انتشار، پذیرفته شده، انتشار آنلاین از تاریخ 09 دی 1402 اصل مقاله (754.02 K)
نوع مقاله: Original paper
شناسه دیجیتال (DOI): 10.22049/cco.2023.28965.1797
نویسندگان
Richard C Brewster¹؛ Christina M Mynhardt^* ²؛ Laura E Teshima²
¹Department of Mathematics and Statistics, Thompson Rivers University
²Department of Mathematics and Statistics, University of Victoria
چکیده
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.
کلیدواژه‌ها
independent domination number؛ graph reconfiguration؛ i-graph

مراجع
[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
آمار تعداد مشاهده مقاله: 113 تعداد دریافت فایل اصل مقاله: 341

سامانه مدیریت نشریات علمی. قدرت گرفته از سیناوب

پیوندهای مفید

آمار

Reconfiguring Minimum Independent Dominating Sets in Graphs