<abstract xmlns="http://www.w3.org/1999/xhtml">

<p>The independent domination number <italic>i</italic>(<italic>G</italic>) of a graph <italic>G</italic> is the minimum cardinality of a maximal independent set of <italic>G</italic>, also called an <italic>i</italic>(<italic>G</italic>)-set. The <italic>i</italic>-graph of <italic>G</italic>, denoted ℐ (<italic>G</italic>), is the graph whose vertices correspond to the <italic>i</italic>(<italic>G</italic>)-sets, and where two <italic>i</italic>(<italic>G</italic>)-sets are adjacent if and only if they differ by two adjacent vertices. Not all graphs are <italic>i</italic>-graph realizable, that is, given a target graph <italic>H</italic>, there does not necessarily exist a source graph <italic>G</italic> such that <italic>H</italic> = ℐ (<italic>G</italic>). We consider a class of graphs called “theta graphs”: a theta graph is the union of three internally disjoint nontrivial paths with the same two distinct end vertices. We characterize theta graphs that are <italic>i</italic>-graph realizable, showing that there are only finitely many that are not. We also characterize those line graphs and claw-free graphs that are <italic>i</italic>-graphs, and show that all 3-connected cubic bipartite planar graphs are <italic>i</italic>-graphs.</p>
</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 ℐ (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. 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 = ℐ (G). We consider a class of graphs called “theta graphs”: a theta graph is the union of three internally disjoint nontrivial paths with the same two distinct end vertices. We characterize theta graphs that are i-graph realizable, showing that there are only finitely many that are not. We also characterize those line graphs and claw-free graphs that are i-graphs, and show that all 3-connected cubic bipartite planar graphs are i-graphs.

The Realizability of Theta Graphs as Reconfiguration Graphs of Minimum Independent Dominating Sets

Annales Mathematicae Silesianae

This work is licensed under the Creative Commons Attribution 4.0 International License.

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,...

The Realizability of Theta Graphs as Reconfiguration Graphs of Minimum Independent Dominating Sets

Published Online: Feb 21, 2024

Page range: -

Received: Jan 17, 2024

DOI: https://doi.org/10.2478/amsil-2024-0002

Keywords
independent domination number, graph reconfiguration, -graph, theta graph

© 2024 R.C. Brewster et al., published by Sciendo

This work is licensed under the Creative Commons Attribution 4.0 International License.

The Realizability of Theta Graphs as Reconfiguration Graphs of Minimum Independent Dominating Sets

Published Online: Feb 21, 2024

Page range: -

Received: Jan 17, 2024

DOI: https://doi.org/10.2478/amsil-2024-0002

Keywordsindependent domination number, graph reconfiguration, -graph, theta graph

© 2024 R.C. Brewster et al., published by Sciendo

This work is licensed under the Creative Commons Attribution 4.0 International License.

Keywords
independent domination number, graph reconfiguration, -graph, theta graph