Haynes, Teresa W.; Henning, Michael A.; van der Merwe, Lucas C. Domination and total domination in complementary prisms. (English) Zbl 1197.05105 J. Comb. Optim. 18, No. 1, 23-37 (2009). Summary: 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}})\}\leq \gamma(G{\overline {G}})\) and \(\max\{\gamma_{t}(G),\gamma_{t}({\overline {G}})\}\leq \gamma_{t}(G{\overline {G}})\), 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. Cited in 19 Documents MSC: 05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) Keywords:Cartesian product; complementary prism; domination; total domination PDFBibTeX XMLCite \textit{T. W. Haynes} et al., J. Comb. Optim. 18, No. 1, 23--37 (2009; Zbl 1197.05105) Full Text: DOI References: [1] Chartrand G, Lesniak L (2005) Graphs and digraphs: fourth edition. Chapman & Hall, London · Zbl 1057.05001 [2] Haynes TW, Hedetniemi ST, Slater PJ (eds) (1998a) Fundamentals of domination in graphs. Marcel Dekker, New York [3] Haynes TW, Hedetniemi ST, Slater PJ (eds) (1998b) Domination in graphs: advanced topics. Marcel Dekker, New York [4] Haynes TW, Henning MA, Slater PJ, van der Merwe LC (2007) The complementary product of two graphs. Bull Inst Comb Appl 51:21–30 · Zbl 1155.05051 [5] Henning MA (2000) Graphs with large total domination number. J Graph Theory 35:21–45 · Zbl 0959.05089 This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.