Reconfiguration of Minimum Independent Dominating Sets in Graphs

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 c a l 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. We show that 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 isomorphic to

m a t h c a l I (G)

. Examples of such graphs include

K_{4} - e

and

K_{2, 3}

. We build a series of tools to show that known

i

-graphs can be used to construct new

i

-graphs and apply these results to build other classes of

i

-graphs, such as block graphs, hypercubes, forests, cacti, and unicyclic graphs.

This page was built for publication: Reconfiguration of Minimum Independent Dominating Sets in Graphs