Article
Full entry |
PDF
(0.2 MB)
Feedback
PDF
(0.2 MB)
Feedback
Keywords:
graphs; domination number; graph’s complement; complement
graphs; domination number; graph’s complement; complement
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$.
References:
[1] C. Berge: Graphes et Hypergraphes. Dunod, Paris, 1970. MR 0357173 | Zbl 0213.25702
[2] J. A. Bondy, U. S. R. Murty: Graph Theory with Applications. Macmillan Press, 1976. MR 0411988
Search
Partner of
