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: