A Note on Connected Dominating Set in Graphs Without Long Paths And Cycles

The ratio of the connected domination number, $γ_c$, and the domination number, $γ$, is strictly bounded from above by 3. It was shown by Zverovich that for every connected $(P_5,C_5)$-free graph, $γ_c = γ$. In this paper, we investigate the interdependence of $γ$ and $γ_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, $γ_c \le γ+ 1$ holds, and there is a family of $(P_6,C_6)$-free graphs with arbitrarily large values of $γ$ attaining this bound. Moreover, for every connected $(P_8,C_8)$-free graph, $γ_c / γ\le 2$, and there is a family of $(P_7,C_7)$-free graphs with arbitrarily large values of $γ$ attaining this bound. In the class of $(P_9,C_9)$-free graphs, the general bound $γ_c / γ\le 3$ is asymptotically sharp.

No reviews yet.

No comments yet.