In a graph G = (V,E), a subset S ⊆ V is a double dominating set if every vertex in V is dominated at least twice. The minimum cardinality of a double dominating set of G is the double domination number. A graph G is double domination edge critical if for any edge uv ε E(Ḡ), the double domination number of G + uv is less than the double domination number of G. We investigate double domination edge critical graphs and characterize the trees and cycles having this property. Then we concentrate on double domination edge critical graphs having small double domination numbers. In particular, we characterize the ones with double domination number three and subfamilies of those with double domination number four.
| Identifer | oai:union.ndltd.org:ETSU/oai:dc.etsu.edu:etsu-works-18427 |
| Date | 01 March 2009 |
| Creators | Haynes, Teresa W., Thacker, Derrick |
| 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.017 seconds