Domination and total domination in complementary prisms
Let G be a graph and (G) over bar be the complement of G. The complementary prism G (G) over bar of G is the graph formed from the disjoint union of G and (G) over bar by adding the edges of a perfect matching between the corresponding vertices of G and (G) over bar. For example, if G is a 5-cycle, then G (G) over bar is the Petersen graph. In this paper we consider domination and total domination numbers of complementary prisms. For any graph G, max{gamma(G),gamma((G) over bar)} <= gamma (G (G) over bar) and max{gamma(t)(G), gamma(t)((G) over bar)} <= gamma(t)(G (G) over bar), where gamma(G) and gamma(t)(G) denote the domination and total domination numbers of G, respectively. Among other results, we characterize the graphs G attaining these lower bounds.
domination total domination complementary prism cartesian product