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.
Identifer | oai:union.ndltd.org:ETSU/oai:dc.etsu.edu:etsu-works-15416 |
Date | 01 December 2013 |
Creators | Desormeaux, Wyatt J., Haynes, Teresa W., Henning, Michael A. |
Publisher | Digital Commons @ East Tennessee State University |
Source Sets | East Tennessee State University |
Detected Language | English |
Type | text |
Source | ETSU Faculty Works |
Page generated in 0.0012 seconds