Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
419369 | Discrete Applied Mathematics | 2013 | 7 Pages |
Abstract
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.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Wyatt J. Desormeaux, Teresa W. Haynes, Michael A. Henning,