The realizability of theta graphs as reconfiguration graphs of minimum independent dominating sets

R. C. Brewster; C. M. Mynhardt; L. E. Teshima

Published: 2024-02-21
Language: EN

2024

The realizability of theta graphs as reconfiguration graphs of minimum independent dominating sets

R. C. Brewster , C. M. Mynhardt

, L. E. Teshima

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.

(EN)

Keywords:

independent domination number , graph reconfiguration , i-graph , theta graph (EN)

Download files

PDF

Citation rules

Brewster, R. C., Mynhardt, C. M., & Teshima, L. E. (2024). The realizability of theta graphs as reconfiguration graphs of minimum independent dominating sets. Annales Mathematicae Silesianae. Retrieved from https://trrest.vot.pl/ojsus/index.php/AMSIL/article/view/17122

References

L.W. Beineke, Characterizations of derived graphs, J. Combinatorial Theory 9 (1970), 129–135.
Google Scholar

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.
Google Scholar

G. Chartrand, L. Lesniak, and P. Zhang, Graphs and Digraphs. 6th edition, Chapman & Hall, , London, 2015.
Google Scholar

T.W. Haynes, S.T. Hedetniemi, and P.J. Slater, Domination in Graphs, Marcel Dekker, New York, 1998.
Google Scholar

T.W. Haynes, S.T. Hedetniemi, and P.J. Slater, Fundamentals of Domination in Graphs, Marcel Dekker, New York, 1998.
Google Scholar

P.J. Heawood, On the four-color map theorem, Quart. J. Pure Math. 29 (1898), 270–285.
Google Scholar

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.
Google Scholar

C.M. Mynhardt and L.E. Teshima, A note on some variations of the γ-graph, J. Combin. Math. Combin. Comput. 104 (2018), 217–230.
Google Scholar

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.
Google Scholar

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.
Google Scholar

D.J.A. Welsh, Euler and bipartite matroids, J. Combinatorial Theory 6 (1969), 375–377.
Google Scholar

R. C. Brewster

Affiliation:

Department of Mathematics and Statistics, Thompson Rivers University Canada

C. M. Mynhardt

kieka@uvic.ca
https://orcid.org/0000-0001-6981-676X

Affiliation:

Department of Mathematics and Statistics, University of Victoria Canada

L. E. Teshima

Affiliation:

Department of Mathematics and Statistics, University of Victoria Canada

2024
Published: 2023-10-26

ISSN: 0860-2107

eISSN: 2391-4238

10.1515/amsil

Publisher

University of Silesia Press

Submit