Reconfiguring dominating sets in minor-closed graph classes (Q2053687)

Let \(G=(V,E)\) be a graph. A set \(S\subseteq V(G)\) is a dominating set, if every vertex in \(V(G)\backslash S\) is adjacent to at least one vertex in \(S\). Given dominating sets \(S\) and \(T\), is there a sequence of dominating sets \(S_0 = 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? If the answer is yes, then \(S\) is said to \(k\)-transform to \(T\). A toroidal graph is a graph that can be embedded on a torus. In other words, the graph's vertices can be placed on a torus such that no edges cross. A graph \(G\) of order \(n\) has a balanced separator of order \(k\) if there is a set \(D\) of at most \(k\) vertices of \(G\) as well as a partition of the vertex set \(V(G)\) of \(G\) into three sets \(D,A\) and \(B\) such that \(|A|,|B|\leq \frac{2n}{3}\), and \(G\) contains no edge between \(A\) and \(B\). The authors prove that there is some positive constant \(c\) and there are toroidal graphs \(G\) of arbitrarily large order \(n\), and two minimum dominating sets \(S\) and \(T\) in \(G\) such that \(S\) \(k\)-transforms to \(T\) only if \(k \geq \max\{|S|,|T|\}+c\sqrt{n}\). Conversely, for every hereditary class \(\mathcal{G}\) that has balanced separators of order \(n\mapsto n^{\alpha}\) for some \(\alpha<1\), they prove that there is some positive constant \(C\) such that, if \(G\) is a graph in \(\mathcal{G}\) of order \(n\), and \(S\) and \(T\) are two dominating sets in \(G\), then \(S\) \(k\)-transforms to \(T\) for \(k = \max\{|S|,|T|\}+\lfloor Cn^{\alpha}\rfloor\).