2026-07-24T05:02:11Z https://drops.dagstuhl.de/oai
oai:drops-oai.dagstuhl.de:13381 2024-03-06T10:51:50Z ddc:004 open_access
Linear Transformations Between Dominating Sets in the TAR-Model Bousquet, Nicolas Joffard, Alice Ouvrard, Paul reconfiguration dominating sets addition removal connectivity diameter minor treewidth Given a graph G and an integer k, a token addition and removal (TAR for short) reconfiguration sequence between two dominating sets D_s and D_t of size at most k is a sequence S = ⟨ Dβ‚€ = D_s, D₁ …, D_𝓁 = D_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 [R. Haas and K. Seyffarth, 2017], 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 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. Schloss Dagstuhl – Leibniz-Zentrum fΓΌr Informatik Nicolas Bousquet and Alice Joffard and Paul Ouvrard 2020 Is Part Of LIPIcs, Volume 181, 31st International Symposium on Algorithms and Computation (ISAAC 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ISAAC.2020.37 urn:nbn:de:0030-drops-133812 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2020.37 eng https://creativecommons.org/licenses/by/3.0/legalcode