Bounds on the connected domination number of a graph

A subset SS of vertices in a graph G=(V,E)G=(V,E) is a connected dominating set of GG if every vertex of V∖SV∖S is adjacent to a vertex in SS and the subgraph induced by SS is connected. The minimum cardinality of a connected dominating set of GG is the connected domination number γc(G)γc(G). The girth g(G)g(G) is the length of a shortest cycle in GG. We show that if GG is a connected graph that contains at least one cycle, then γc(G)≥g(G)−2γc(G)≥g(G)−2, and we characterize the graphs obtaining equality in this bound. We also establish various upper bounds on the connected domination number of a graph, as well as Nordhaus–Gaddum type results.