Domination and total domination in complementary prisms

Autor: Michael A. Henning, Teresa W. Haynes, Lucas C. van der Merwe
Rok vydání: 2008
Předmět:
Zdroj: Journal of Combinatorial Optimization. 18:23-37
ISSN: 1573-2886
1382-6905
DOI: 10.1007/s10878-007-9135-8
Popis: Let G be a graph and ${\overline {G}}$ be the complement of G. The complementary prism $G{\overline {G}}$ of G is the graph formed from the disjoint union of G and ${\overline {G}}$ by adding the edges of a perfect matching between the corresponding vertices of G and ${\overline {G}}$ . For example, if G is a 5-cycle, then $G{\overline {G}}$ 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({\overline {G}})\}\le \gamma(G{\overline {G}})$ and $\max\{\gamma_{t}(G),\gamma_{t}({\overline {G}})\}\le \gamma_{t}(G{\overline {G}})$ , where γ(G) and γ t (G) denote the domination and total domination numbers of G, respectively. Among other results, we characterize the graphs G attaining these lower bounds.
Databáze: OpenAIRE
Externí odkaz: