Independent Domination in Complementary Prisms

Document Type

Article

Publication Date

7-1-2013

Description

The complementary prism of a graph G is the graph formed from a disjoint union of G and its complement ̄G by adding the edges of a perfect matching between the corresponding vertices of G and G. We study independent domination numbers of complementary prisms. Exact values are determined for complementary prisms of paths, complete bipartite graphs, and subdivided stars. A natural lower bound on the independent domination number of a complementary prism is given, and graphs attaining this bound axe characterized. Then we show that the independent domination number behaves somewhat differently in complementary prisms than the domination and total domination numbers. We conclude with a sharp upper bound.

This document is currently not available here.

Share

COinS