|
|
reconfiguring minimum independent dominating sets in graphs
|
|
|
|
|
نویسنده
|
brewster richard ,mynhardt christina ,teshima laura
|
منبع
|
communications in combinatorics and optimization - 2024 - دوره : 9 - شماره : 3 - صفحه:389 -411
|
چکیده
|
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.
|
کلیدواژه
|
independent domination number ,graph reconfiguration ,i-graph
|
آدرس
|
thompson rivers university, department of mathematics and statistics, canada, university of victoria, department of mathematics and statistics, canada, university of victoria, department of mathematics and statistics, canada
|
پست الکترونیکی
|
lteshima@uvic.ca
|
|
|
|
|
|
|
|
|
|
|
|
Authors
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|