Restrained Domination in Complementary Prisms
Document Type
Article
Publication Date
11-1-2011
Description
The complementary prism GḠ of a graph G is formed from the disjoint union of G and its complement G by adding the edges of a perfect matching between the corresponding vertices of G and Ḡ. A set S ⊆ V(G) is a restrained dominating set of G if for every v € V(G) \S, v is adjacent to a vertex in S and a vertex in V(G) \S. The restrained domination number of G is the minimum cardinality of a restrained dominating set of G. We study restrained domination of complementary prisms. In particular, we establish lower and upper bounds on the restrained domination number of GḠ, show that the restrained domination number can be attained for all values between these bounds, and characterize the graphs which attain the lower bound.
Citation Information
Desormeaux, Wyatt J.; and Haynes, Teresa W.. 2011. Restrained Domination in Complementary Prisms. Utilitas Mathematica. Vol.86 267-278. ISSN: 0315-3681