×

Domination and total domination in complementary prisms. (English) Zbl 1197.05105

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.

MSC:

05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
PDFBibTeX XMLCite
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.