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.

This document is currently not available here.

Share

COinS