TY - JOUR
ID - 14682
TI - Reconfiguring Minimum Independent Dominating Sets in Graphs
JO - Communications in Combinatorics and Optimization
JA - CCO
LA - en
SN - 2538-2128
AU - Brewster, Richard C
AU - Mynhardt, Christina M
AU - Teshima, Laura E
AD - Department of Mathematics and Statistics, Thompson Rivers University, 805 TRU Way,
Kamloops, B.C., Canada
AD - Department of Mathematics and Statistics, University of Victoria, PO BOX 1700 STN CSC, Victoria, B.C. Canada
Y1 - 2024
PY - 2024
VL - 9
IS - 3
SP - 389
EP - 411
KW - independent domination number
KW - graph reconfiguration
KW - i-graph
DO - 10.22049/cco.2023.28965.1797
N2 - 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 $\mathscr{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 seed graph $G$ such that $H \cong \mathscr{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.
UR - http://comb-opt.azaruniv.ac.ir/article_14682.html
L1 - http://comb-opt.azaruniv.ac.ir/article_14682_00b259f42904b5f195c552f0b64e33f8.pdf
ER -