Restrained domination in complementary prisms

Abstract

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.