文章基本信息
- 标题：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
