Bounds on the Connected Domination Number of a Graph
Document Type
Article
Publication Date
12-1-2013
Description
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 γ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 γ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.
Citation Information
Desormeaux, Wyatt J.; Haynes, Teresa W.; and Henning, Michael A.. 2013. Bounds on the Connected Domination Number of a Graph. Discrete Applied Mathematics. Vol.161(18). 2925-2931. https://doi.org/10.1016/j.dam.2013.06.023 ISSN: 0166-218X