论文标题
焦油模型中的主导集之间的线性变换
Linear transformations between dominating sets in the TAR-model
论文作者
论文摘要
给定图形$ g $和一个整数$ k $，一个令牌的添加和删除（简称{\ sf tar}）在两个主导集合之间的重新配置顺序\ ldots，d_ \ ell = d _ {\ sf t} \ rangle $的$ g $集合，使得任何两个连续的主导集都因一个顶点的添加或删除而有所不同，并且没有主导集的大小大于$ 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. 然后，我们通过证明$ k _ {\ ell} $ - 次要的免费图形来改进几个图类别的结果 - 只要$ k \geγ（g）+o（\ ell \ sqrt {\ el \ sqrt {\ log \ ell}）$，对于平面图。最后，我们表明，如果$ k =γ（g）+TW（g）+1 $，则在任何一对主导集之间也存在线性转换。
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= \langle D_0 = D_{\sf s}, D_1 \ldots, D_\ell = D_{\sf t} \rangle$ 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_{\ell}$-minor free graph as long as $k \ge Γ(G)+O(\ell \sqrt{\log \ell})$ and for planar graphs whenever $k \ge Γ(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.
