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.