| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 418286 | Discrete Applied Mathematics | 2014 | 7 Pages |
In the first part of this paper, we investigate the interdependence of the connected domination number γc(G)γc(G) and the domination number γ(G)γ(G) in some hereditary graph classes. We prove the following results:•A connected graph GG is (P6,C6)(P6,C6)-free if and only if γc(H)⩽γ(H)+1γc(H)⩽γ(H)+1 for every connected induced subgraph HH of GG. Moreover, there are (P6,C6)(P6,C6)-free graphs with arbitrarily large domination number attaining this bound.•For every connected (P8,C8)(P8,C8)-free graph GG, it holds that γc(G)/γ(G)⩽2γc(G)/γ(G)⩽2, and this bound is attained by connected (P7,C7)(P7,C7)-free graphs with arbitrarily large domination number. In particular, the bound γc(G)⩽2γ(G)γc(G)⩽2γ(G) is best possible even in the class of connected (P7,C7)(P7,C7)-free graphs.•The general upper bound of γc(G)/γ(G)<3γc(G)/γ(G)<3 is asymptotically sharp on connected (P9,C9)(P9,C9)-free graphs.In the second part, we prove that the following decision problem is Θ2p-complete, for every fixed rational 1
