The realizability of theta graphs as reconfiguration graphs of minimum independent dominating sets
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 𝓣(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. Not all graphs are i-graph realizable, that is, given a target graph H, there does not necessarily exist a source graph G such that H ≅ 𝓣(G). We consider a class of graphs called “theta graphs”: a theta graph is the union of three internally disjoint nontrivial paths with the same two distinct end vertices. We characterize theta graphs that are i-graph realizable, showing that there are only finitely many that are not. We also characterize those line graphs and claw-free graphs that are i-graphs, and show that all 3-connected cubic bipartite planar graphs are i-graphs.
Keywords
independent domination number; graph reconfiguration; i-graph; theta graph
References
L.W. Beineke, Characterizations of derived graphs, J. Combinatorial Theory 9 (1970), 129–135.
R.C. Brewster, C.M. Mynhardt, and L.E. Teshima, Reconfiguration of minimum independent dominating sets in graphs, Commun. Comb. Optim. DOI: 10.22049/cco.2023.28965.1797.
G. Chartrand, L. Lesniak, and P. Zhang, Graphs and Digraphs. 6th edition, Chapman & Hall, , London, 2015.
T.W. Haynes, S.T. Hedetniemi, and P.J. Slater, Domination in Graphs, Marcel Dekker, New York, 1998.
T.W. Haynes, S.T. Hedetniemi, and P.J. Slater, Fundamentals of Domination in Graphs, Marcel Dekker, New York, 1998.
P.J. Heawood, On the four-color map theorem, Quart. J. Pure Math. 29 (1898), 270–285.
C.M. Mynhardt and S. Nasserasr, Reconfiguration of colourings and dominating sets in graphs, in: F. Chung et al. (eds.), 50 years of Combinatorics, Graph Theory, and Computing, Discrete Math. Appl. (Boca Raton), CRC Press, Boca Raton, FL, 2020, pp. 171–191.
C.M. Mynhardt and L.E. Teshima, A note on some variations of the γ-graph, J. Combin. Math. Combin. Comput. 104 (2018), 217–230.
L.E. Teshima, The i-Graph and Other Variations on the γ-Graph, PhD thesis, University of Victoria, 2022. Avaliable at https://dspace.library.uvic.ca.
M.-T. Tsai and D.B. West, A new proof of 3-colorability of Eulerian triangulations, Ars Math. Contemp. 4 (2011), no. 1, 73–77.
D.J.A. Welsh, Euler and bipartite matroids, J. Combinatorial Theory 6 (1969), 375–377.
Department of Mathematics and Statistics, Thompson Rivers University Canada
Department of Mathematics and Statistics, University of Victoria Canada
https://orcid.org/0000-0001-6981-676X
Department of Mathematics and Statistics, University of Victoria Canada
The Copyright Holders of the submitted text are the Author and the Journal. The Reader is granted the right to use the pdf documents under the provisions of the Creative Commons 4.0 International License: Attribution (CC BY). The user can copy and redistribute the material in any medium or format and remix, transform, and build upon the material for any purpose.
- License
This journal provides immediate open access to its content under the Creative Commons BY 4.0 license (http://creativecommons.org/licenses/by/4.0/). Authors who publish with this journal retain all copyrights and agree to the terms of the above-mentioned CC BY 4.0 license. - Author’s Warranties
The author warrants that the article is original, written by stated author/s, has not been published before, contains no unlawful statements, does not infringe the rights of others, is subject to copyright that is vested exclusively in the author and free of any third party rights, and that any necessary written permissions to quote from other sources have been obtained by the author/s. - User Rights
Under the Creative Commons Attribution license, the users are free to share (copy, distribute and transmit the contribution) and adapt (remix, transform, and build upon the material) the article for any purpose, provided they attribute the contribution in the manner specified by the author or licensor. - Co-Authorship
If the article was prepared jointly with other authors, the signatory of this form warrants that he/she has been authorized by all co-authors to sign this agreement on their behalf, and agrees to inform his/her co-authors of the terms of this agreement.
