آمار
| تعداد نشریات | 5 |
| تعداد شمارهها | 111 |
| تعداد مقالات | 1,247 |
| تعداد مشاهده مقاله | 1,199,552 |
| تعداد دریافت فایل اصل مقاله | 1,060,264 |
Reconfiguring Minimum Independent Dominating Sets in Graphs | ||
| Communications in Combinatorics and Optimization | ||
| مقاله 1، دوره 9، شماره 3، آذر 2024، صفحه 389-411 اصل مقاله (740.93 K) | ||
| نوع مقاله: Original paper | ||
| شناسه دیجیتال (DOI): 10.22049/cco.2023.28965.1797 | ||
| نویسندگان | ||
| Richard C Brewster1؛ Christina M Mynhardt* 2؛ Laura E Teshima2 | ||
| 1Department of Mathematics and Statistics, Thompson Rivers University, 805 TRU Way, Kamloops, B.C., Canada | ||
| 2Department of Mathematics and Statistics, University of Victoria, PO BOX 1700 STN CSC, Victoria, B.C. Canada | ||
| چکیده | ||
| 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 | ||
|
آمار تعداد مشاهده مقاله: 337 تعداد دریافت فایل اصل مقاله: 663 |
||