Double Domination in Complementary Prisms
Document Type
Article
Publication Date
7-1-2013
Description
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.
Citation Information
Desormeaux, Wyatt J.; Haynes, Teresa W.; and Vaughan, Lamont. 2013. Double Domination in Complementary Prisms. Utilitas Mathematica. Vol.91 131-142. ISSN: 0315-3681