Reconfiguring dominating sets in minor-closed graph classes

2020/05/28 by Rautenbach, Dieter, Redl, Johannes
#Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.2005.13844

Abstract

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₀,…,D_ℓ of dominating sets in G such that D=D₀, D'=D_ℓ, |D_i|≤ k for every i∈ \ 0,1,…,ℓ\, and D_i arises from D_i-1 by adding or removing one vertex for every i∈ \ 1,…,ℓ\. 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≥ max\ |D|,|D'|\+c√(n). Conversely, for every hereditary class \cal G that has balanced separators of order n↦ n^α for some α<1, we prove that there is some positive constant C such that, if G is a graph in \cal 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^α\rfloor.

Related

• Linear transformations between dominating sets in the TAR-model
• Dominating sets reconfiguration under token sliding
• Reconfiguration graphs for minimal domination sets
• The k-Dominating Graph
• Reconfiguration of Dominating Sets