Bounds on the connected domination number of a graph

A subset S of vertices in a graph G = (V, E) is a connected dominating set of G if every vertex of V\S is adjacent to a vertex in S and the subgraph induced by S is connected. The minimum cardinality of a connected dominating set of G is the connected domination number gamma(c)(G) The girth g(G) is the length of a shortest cycle in G. We show that if G is a connected graph that contains at least one cycle, then gamma(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. (C) 2013 Elsevier B.V. All rights reserved.