Previous |  Up |  Next


Title: A note on the domination number of a graph and its complement (English)
Author: Marcu, Dănuţ
Language: English
Journal: Mathematica Bohemica
ISSN: 0862-7959 (print)
ISSN: 2464-7136 (online)
Volume: 126
Issue: 1
Year: 2001
Pages: 63-65
Summary lang: English
Category: math
Summary: If $G$ is a simple graph of size $n$ without isolated vertices and $\overline{G}$ is its complement, we show that the domination numbers of $G$ and $\overline{G}$ satisfy \[ \gamma (G) + \gamma (\overline{G}) \le \left\rbrace \begin{array}{ll}n-\delta + 2 \quad \text{if} \quad \gamma (G) > 3, \delta + 3 \quad \text{if} \quad \gamma (\overline{G}) > 3, \end{array}\right.\] where $\delta $ is the minimum degree of vertices in $G$. (English)
Keyword: graphs
Keyword: domination number
Keyword: graph’s complement
Keyword: complement
MSC: 05C40
MSC: 05C69
idZBL: Zbl 0977.05097
idMR: MR1826471
DOI: 10.21136/MB.2001.133925
Date available: 2009-09-24T21:47:20Z
Last updated: 2020-07-29
Stable URL:
Reference: [1] C. Berge: Graphes et Hypergraphes.Dunod, Paris, 1970. Zbl 0213.25702, MR 0357173
Reference: [2] J. A. Bondy, U. S. R. Murty: Graph Theory with Applications.Macmillan Press, 1976. MR 0411988


Files Size Format View
MathBohem_126-2001-1_5.pdf 250.2Kb application/pdf View/Open
Back to standard record
Partner of
EuDML logo