Name
Abstract | ||
|---|---|---|
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. |
Year | Venue | Field |
|---|---|---|
2013 | CoRR | Connected domination,Graph,Discrete mathematics,Combinatorics,Connected dominating set,Domination analysis,Arbitrarily large,Mathematics,Bounded function |
DocType | Volume | Citations |
Journal | abs/1303.2868 | 3 |
PageRank | References | Authors |
0.50 | 3 | 2 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Eglantine Camby | 1 | 16 | 4.02 |
| Oliver Schaudt | 2 | 95 | 21.74 |