The $i$-Graphs of Paths and Cycles

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 $\mathcal{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. Although 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\cong \mathcal{I}(G)$, all graphs have $i$-graphs. We determine the $i$-graphs of paths and cycles and, in the case of cycles, discuss the Hamiltonicity of these $i$-graphs.

19 pages, 11 figures