# Introduction to Reconfiguration
## 7 Other Structural Problems  
In other work, various properties of reconfiguration graphs have been investigated, both towards an understanding of connectivity or diameter (such as the characterization of isolated vertices [105], also known as _frozen configurations_[31]) and in their own right. Most work on such questions has focused on Dominating Set Reconfiguration and \(k\)-Coloring Reconfiguration, including variants in which \(j\) vertices can be colored in a single reconfiguration step [20] as well as one in which only _canonical colorings_, non-isomorphic colorings that are lexicographically least under an ordering of the vertices, are considered [106]. Results have also been obtained for Shortest Path Reconfiguration[107], Independent Set Reconfiguration[108], and Token Sliding[109], as defined in Section 9.2. Examples of properties that have been studied include chromatic number [109], Hamiltonicity [109; 106; 101; 110; 111; 20], and girth [107; 113], often in service of determining limits on the classes of graphs represented by reconfiguration graphs [108; 113; 114; 115]. For a source problem in which the instance is a graph, one can also identify when the reconfiguration graph for an instance is isomorphic to the instance itself [114; 115].  
In the remainder of this section, we focus on Dominating Set (the problem of determining a set of vertices such that each vertex in the graph is either in the set or the neighbor of a vertex in the set); its wide applicability and amenability to variants has led to significant interest in reconfiguration graphs and their structure. Two different graphs with similar names have been based on the _domination number_, where \(\gamma(G)\) is the minimum cardinality of a dominating set of \(G\) and a \(\gamma\)_set_ is a dominating set of minimum cardinality. The graph \(\gamma\cdot G\)[116] uses \(k=\gamma(G)\) under TJ, whereas the \(\gamma\)-graph of \(G\) uses \(k=\gamma(G)\) under TS [117], later considered for different variants such as the total dominating number, paired domination number, and connected dominating number [118]. Work on both the TJ model [119; 120; 121; 122; 123; 124; 125] and the TS model [126] has focused on characterizing which graphs are gamma graphs under the various definitions.  
[PERSON] and [PERSON] considered a reconfiguration graph in which solutions are not limited to minimum cardinality dominating sets; their \(k\)_-dominating graph_ is a reconfiguration graph under TAR in which each solution is a dominating set of size at most \(k\)[114]. For \(\Gamma(G)\), the _upper domination number_ (the maximum cardinality of a minimal dominating set of \(G\)), the connectivity of the \(k\)-dominating graph has been shown for the following cases:  
* \(k\geq\min\{|V(G)|-1,\Gamma(G)+\gamma(G)\}\)[114],
* bipartite and chordal, when \(k\geq\Gamma(G)+1\)[114],
* \(k=n-\mu\) and there is a matching of cardinality at least \(\mu+1\)[127],
* \(k=\Gamma(G)+1\) for certain classes of well-covered graphs [128],
* \(k=\Gamma(G)+1\) for graphs that are both perfect and irredundant perfect [128].  
In contrast, the \(k\)-dominating graph can be disconnected for \(k=\Gamma(G)+1\), even for planar, bounded tree-width, or \(b\)-partite for \(b\geq 3\)[127]. In addition, there is an infinite family of graphs with exponential diameter for \(\gamma(G)+1\)[127].  
Under TAR, the reachability problem is PSPACE-complete even for graphs of bounded bandwidth, split graphs, planar graphs, and bipartite graphs [50], whereas linear-time algorithms have been developed for cographs, trees, and interval graphs [50]. Although \(W[1]\)-hard when parameterized by \(k\), the problem is fixed-parameter tractable when parameterized by \(k\) when the input graph does not contain large bicliques (including bounded degeneracy and nowhere dense graphs) [74].