Geodesic
A note on the domination number of a graph and its complement
Mathematica Bohemica, Tome 126 (2001) no. 1, pp. 63-65

Voir la notice de l'article provenant de la source Czech Digital Mathematics Library

MR Zbl
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$.
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$.
DOI : 10.21136/MB.2001.133925
Classification : 05C40, 05C69
Keywords: graphs; domination number; graph’s complement; complement 
Marcu, Dănuţ. A note on the domination number of a graph and its complement. Mathematica Bohemica, Tome 126 (2001) no. 1, pp. 63-65. doi: 10.21136/MB.2001.133925
@article{10_21136_MB_2001_133925,
     author = {Marcu, D\u{a}nu\c{t}},
     title = {A note on the domination number of a graph and its complement},
     journal = {Mathematica Bohemica},
     pages = {63--65},
     year = {2001},
     volume = {126},
     number = {1},
     doi = {10.21136/MB.2001.133925},
     mrnumber = {1826471},
     zbl = {0977.05097},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.21136/MB.2001.133925/}
}
TY  - JOUR
AU  - Marcu, Dănuţ
TI  - A note on the domination number of a graph and its complement
JO  - Mathematica Bohemica
PY  - 2001
SP  - 63
EP  - 65
VL  - 126
IS  - 1
UR  - http://geodesic.mathdoc.fr/articles/10.21136/MB.2001.133925/
DO  - 10.21136/MB.2001.133925
LA  - en
ID  - 10_21136_MB_2001_133925
ER  - 
%0 Journal Article
%A Marcu, Dănuţ
%T A note on the domination number of a graph and its complement
%J Mathematica Bohemica
%D 2001
%P 63-65
%V 126
%N 1
%U http://geodesic.mathdoc.fr/articles/10.21136/MB.2001.133925/
%R 10.21136/MB.2001.133925
%G en
%F 10_21136_MB_2001_133925

[1] C. Berge: Graphes et Hypergraphes. Dunod, Paris, 1970. | MR | Zbl

[2] J. A. Bondy, U. S. R. Murty: Graph Theory with Applications. Macmillan Press, 1976. | MR

Cité par Sources :