MATHEMATICA BOHEMICA, Vol. 126, No. 1, pp. 63-65 (2001)

A note on the domination number of a graph
and its complement

Danut Marcu

Danut Marcu, Str. Pasului 3, Sect. 2, 70241-Bucharest, Romania

Abstract: 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 \cases n-\delta + 2 \quad \text {if} \quad \gamma (G) > 3,
\delta + 3 \quad \text {if} \quad \gamma (\overline G) > 3, \endcases $$ where $\delta$ is the minimum degree of vertices in $G$.

Keywords: graphs, domination number, graph's complement

Classification (MSC2000): 05C40

Full text of the article:

[Previous Article] [Next Article] [Contents of this Number]
© 2005 ELibM and FIZ Karlsruhe / Zentralblatt MATH for the EMIS Electronic Edition