2020/06/30 by Bousquet, Nicolas, Joffard, Alice, Ouvrard, Paul
#Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2006.16726
Given a graph G and an integer k, a token addition and removal (\sf TAR for short) reconfiguration sequence between two dominating sets D\sf s and D\sf t of size at most k is a sequence S= ⟨ D0 = D\sf s, D1 …, D_ℓ = D\sf t ⟩ of dominating sets of G such that any two consecutive dominating sets differ by the addition or deletion of one vertex, and no dominating set has size bigger than k. We first improve a result of Haas and Seyffarth, by showing that if k=Γ(G)+α(G)-1 (where Γ(G) is the maximum size of a minimal dominating set and α(G) the maximum size of an independent set), then there exists a linear \sf TAR reconfiguration sequence between any pair of dominating sets. We then improve these results on several graph classes by showing that the same holds for Kℓ-minor free graph as long as k ≥ Γ(G)+O(ℓ √(log ℓ)) and for planar graphs whenever k ≥ Γ(G)+3. Finally, we show that if k=Γ(G)+tw(G)+1, then there also exists a linear transformation between any pair of dominating sets.