Double Domination in Complementary Prisms

作者：Desormeaux Wyatt J^*; Haynes Teresa W; Vaughan Lamont

来源：Utilitas Mathematica, 2013, 91: 131-142.

• cartesian product
• complementary prism
• double domination number
• complementary product

The complementary prism G (G) over bar of a graph G is formed from the disjoint union of G and its complement (G) over bar by adding the edges of a perfect matching between the corresponding vertices of G and (G) over bar. A set S subset of V(G) is a double dominating set of G if for every v is an element of V(G)\S, v is adjacent to at least two vertices of S, and for every w is an element of 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 (G) over bar and show that all values between these bounds are attainable.

• 出版日期2013-7