Reconfiguration graphs for dominating sets (Q2073197)

If \(G\) is a graph, then the \(k\)-dominating graph \(D_k(G)\) of \(G\) is the graph whose vertices correspond to the dominating sets of \(G\) that have cardinality at most \(k\), two vertices of \(D_k(G)\) being adjacent if and only if the corresponding dominating sets of \(G\) differ by either adding or deleting a single vertex. The introduction of the \(k\)-dominating graphs was motivated by similar studied on graph colorings, by a reconfiguration problem (which asks whether a feasible solution to a problem can be transformed into another by some allowable set of moves, while maintaining feasibility at all steps), and in general to further understand the relationships between dominating sets of a graph. For instance, given dominating sets \(S\) and \(T\), is there a sequence of dominating sets \(S = S_1, S_2,\ldots, S_k = T\) such that each \(S_{i+1}\) is obtained from \(S_i\) by deleting or adding a single vertex? In Section 2 of this chapter, the authors state previous work on reconfiguration of dominating sets. In Section 3, they investigate properties of the dominating graph, \(D(G)\), i.e., the \(k\)-dominating graph when \(k=|V (G)|\). For example, they prove that if \(G\) is a connected graph on \(n\geq 2\) vertices, then \(D(G)\) has diameter \(n\). Also, the graph \(D(G)\) has a cut-vertex if and only if \(G\cong K_{1,n}\) for some natural \(n\). In Section 4, they focus their attention on Hamilton paths of dominating graphs. For the entire collection see [Zbl 1470.05006].