The Realizability of Theta Graphs as Reconfiguration Graphs of Minimum Independent Dominating Sets

MaRDI QIDQ6438279zbMATH OpenFDO

Authors Richard C. Brewster, Christina M. Mynhardt, Laura E. Teshima

Publication date 28 May 2023

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

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$ 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$ is the $i$-graph of $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.

This page was built for publication: The Realizability of Theta Graphs as Reconfiguration Graphs of Minimum Independent Dominating Sets

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6438279)