Bounds on the connected domination number of a graph
A subset S S of vertices in a graph G=(V,E) G = ( V , E ) is a connected dominating set of G G if every vertex of V?S V ? S is adjacent to a vertex in S S and the subgraph induced by S S is connected. The minimum cardinality of a connected dominating set of G G is the connected domination number ?c(G) ? c ( G ) . The girth g(G) g ( G ) is the length of a shortest cycle in G G . We show that if G G 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 NordhausGaddum type results.
connected domination domination girth