A Note on Connected Dominating Set in Graphs Without Long Paths And Cycles
A Note on Connected Dominating Set in Graphs Without Long Paths And Cycles
复制标题
关于无长路径和循环图中连通支配集的注记
DOI：
--
复制
发表时间：
2013
期刊：
影响因子：
--
通讯作者：
Oliver Schaudt
中科院分区：
文献类型：
--
作者：
Eglantine Camby;Oliver Schaudt
连通控制数$gamma_c$和控制数$gamma$的比严格上界为3。Zverovich证明了：对任意连通$（P_5，C_5）$-free图，$gamma_c = gamma$.
本文研究了$（P_k，C_k）$-free图类中$gamma$和$gamma_c$的相互依赖性，其中$k ∈ 6$.本文证明了对每一个连通的$（P_6，C_6）$-free图，$gamma_c le gamma + 1$成立，并且存在一族$（P_6，C_6）$-free图，其任意大的$gamma$达到这个界。此外，对每一个连通的$（P8，C8）$-free图，$gamma_c / gamma le 2$，并且存在一族$（P7，C7）$-free图，其任意大的$gamma$值达到这个界。在$（P_9，C_9）$-free图类中，一般界$gamma_c / gamma le 3$是渐近尖的.
The ratio of the connected domination number, $gamma_c$, and the domination number, $gamma$, is strictly bounded from above by 3. It was shown by Zverovich that for every connected $(P_5,C_5)$-free graph, $gamma_c = gamma$.
In this paper, we investigate the interdependence of $gamma$ and $gamma_c$ in the class of $(P_k,C_k)$-free graphs, for $k ge 6$. We prove that for every connected $(P_6,C_6)$-free graph, $gamma_c le gamma + 1$ holds, and there is a family of $(P_6,C_6)$-free graphs with arbitrarily large values of $gamma$ attaining this bound. Moreover, for every connected $(P_8,C_8)$-free graph, $gamma_c / gamma le 2$, and there is a family of $(P_7,C_7)$-free graphs with arbitrarily large values of $gamma$ attaining this bound. In the class of $(P_9,C_9)$-free graphs, the general bound $gamma_c / gamma le 3$ is asymptotically sharp.