文章基本信息

标题：Linear Transformations Between Dominating Sets in the TAR-Model
本地全文：下载
作者：Nicolas Bousquet ; Alice Joffard ; Paul Ouvrard 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2020
卷号：181
页码：1-14
DOI：10.4230/LIPIcs.ISAAC.2020.37
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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 = âY¨ Dâ, = D_s, Dâ, â¦, D_ð" = D_t âY© 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(ð" â^S(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.
关键词：reconfiguration; dominating sets; addition removal; connectivity; diameter; minor; treewidth