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

m a t h s c r 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 c o n g m a t h s c r 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.

This page was built for publication: The $i$-Graphs of Paths and Cycles