The complementary prism GḠ of a graph G is formed from the disjoint union of G and its complement Ḡ by adding the edges of a perfect matching between the corresponding vertices of G and Ḡ. A set S ⊆ V(G) is a double dominating set of G if for every v ∈ V(G)\S, v is adjacent to at least two vertices of S, and for every w ∈ S, w is adjacent to at least one vertex of S. The double domination number of G is the minimum cardinality of a double dominating set of G. We begin by determining the double domination number of complementary prisms of paths and cycles. Then we characterize the graphs G whose complementary prisms have small double domination numbers. Finally, we establish lower and upper bounds on the double domination number of GḠ and show that all values between these bounds are attainable.
| Identifer | oai:union.ndltd.org:ETSU/oai:dc.etsu.edu:etsu-works-16041 |
| Date | 01 July 2013 |
| Creators | Desormeaux, Wyatt J., Haynes, Teresa W., Vaughan, Lamont |
| 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