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

Marcu, Dănuţ. "A note on the domination number of a graph and its complement." Mathematica Bohemica 126.1 (2001): 63-65. <http://eudml.org/doc/248850>.

@article{Marcu2001,
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 \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$.},
author = {Marcu, Dănuţ},
journal = {Mathematica Bohemica},
keywords = {graphs; domination number; graph’s complement; complement; domination number; complement},
language = {eng},
number = {1},
pages = {63-65},
publisher = {Institute of Mathematics, Academy of Sciences of the Czech Republic},
title = {A note on the domination number of a graph and its complement},
url = {http://eudml.org/doc/248850},
volume = {126},
year = {2001},
}

TY - JOUR
AU - Marcu, Dănuţ
TI - A note on the domination number of a graph and its complement
JO - Mathematica Bohemica
PY - 2001
PB - Institute of Mathematics, Academy of Sciences of the Czech Republic
VL - 126
IS - 1
SP - 63
EP - 65
AB - 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$.
LA - eng
KW - graphs; domination number; graph’s complement; complement; domination number; complement
UR - http://eudml.org/doc/248850
ER -