Reconfiguring Dominating Sets in Minor-Closed Graph Classes

For a graph G, two dominating sets D and $$D'$$ in G, and a non-negative integer k, the set D is said to k-transform to $$D'$$ if there is a sequence $$D_0,\ldots ,D_\ell $$ of dominating sets in G such that $$D=D_0$$ , $$D'=D_\ell $$ , $$|D_i|\le k$$ for every $$i\in \{ 0,1,\ldots ,\ell \}$$ , and $$D_i$$ arises from $$D_{i-1}$$ by adding or removing one vertex for every $$i\in \{ 1,\ldots ,\ell \}$$ . We prove that there is some positive constant c and there are toroidal graphs G of arbitrarily large order n, and two minimum dominating sets D and $$D'$$ in G such that D k-transforms to $$D'$$ only if $$k\ge \max \{ |D|,|D'|\}+c\sqrt{n}$$ . Conversely, for every hereditary class $$\mathcal{G}$$ that has balanced separators of order $$n\mapsto n^\alpha $$ for some $$\alpha <1$$ , we prove that there is some positive constant C such that, if G is a graph in $$\mathcal{G}$$ of order n, and D and $$D'$$ are two dominating sets in G, then D k-transforms to $$D'$$ for $$k=\max \{ |D|,|D'|\}+\lfloor Cn^\alpha \rfloor $$ .