Nordhaus-Gaddum inequalities for domination in graphs
type: Item
instance of: scholarly article
title: Nordhaus-Gaddum inequalities for domination in graphs
zbMATH Open document ID: 0856.05053
DOI: 10.1016/0012-365X(94)00373-Q
author: Frank Harary
author: Teresa W. Haynes
published in: Discrete Mathematics
publication date: 1997-02-17T00:00:00Z
review text: A subset \(D\) of the vertex set \(V(G)\) of a graph \(G\) is called doubly dominating, if each vertex \(x\) of \(G\) either is in \(D\) and is adjacent to at least one other vertex of \(D\), or is adjacent to at least two vertices of \(D\). The minimum number of vertices of a doubly dominating set is the double domination number \(\text{dd} (G)\) of \(G\). The paper begins by a survey of results of other authors which concern results of Nordhaus-Gaddum type for various domination parameters. Then four theorems are proved. The first theorem is of Nordhaus-Gaddum type and holds for graphs without isolated vertices; it says that \(6 \leq \text{dd} (G) + \text{dd} (\overline G) \leq 2n\), and \(9 \leq \text{dd} (G) \cdot \text{dd} (\overline G) \leq n^2\), where \(\overline G\) is the complement of \(G\) and \(n\) is the number of vertices of \(G\). The fourth theorem says that if the (usual) domination numbers of \(G\) and \(\overline G\) are at least 5, then \(\text{dd} (G) + \text{dd} (\overline G) \leq n - \Delta + \delta - 1\), where \(\Delta\) is the maximum degree and \(\delta\) is the minimum degree of \(G\). Also the remaining theorems are in the form of inequalities. A conjecture is suggested.
reviewed by: Bohdan Zelinka
Mathematics Subject Classification ID: 05C35
zbMATH DE Number: 932529
zbMATH Keywords: doubly dominating set
zbMATH Keywords: double domination number
zbMATH Keywords: Nordhaus-Gaddum type
zbMATH Keywords: inequalities
zbMATH Keywords: conjecture
MaRDI profile type: Publication
cites work: Vertex domination-critical graphs
cites work: Total domination in graphs
cites work: Towards a theory of domination in graphs
cites work: Parallel concepts in graph theory
cites work: Q4552196
cites work: Q3340900
cites work: Bibliography on domination in graphs and some basic definitions of domination parameters
cites work: Q5632603
cites work: On connected cutfree domination in graphs
cites work: Q3758884
cites work: Q3933018
cites work: On Complementary Graphs
cites work: Q3895508
cites work: Q4873774
full work available at URL: 0012-365x(94)00373-q
OpenAlex ID: W1983373780
description: scientific article; zbMATH DE number 932529