| Title:
|
A note on the domination number of a graph and its complement (English) |
| Author:
|
Marcu, Dănuţ |
| Language:
|
English |
| Journal:
|
Mathematica Bohemica |
| ISSN:
|
0862-7959 (print) |
| ISSN:
|
2464-7136 (online) |
| Volume:
|
126 |
| Issue:
|
1 |
| Year:
|
2001 |
| Pages:
|
63-65 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| 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$. (English) |
| Keyword:
|
graphs |
| Keyword:
|
domination number |
| Keyword:
|
graph’s complement |
| Keyword:
|
complement |
| MSC:
|
05C40 |
| MSC:
|
05C69 |
| idZBL:
|
Zbl 0977.05097 |
| idMR:
|
MR1826471 |
| DOI:
|
10.21136/MB.2001.133925 |
| . |
| Date available:
|
2009-09-24T21:47:20Z |
| Last updated:
|
2020-07-29 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/133925 |
| . |
| Reference:
|
[1] C. Berge: Graphes et Hypergraphes.Dunod, Paris, 1970. Zbl 0213.25702, MR 0357173 |
| Reference:
|
[2] J. A. Bondy, U. S. R. Murty: Graph Theory with Applications.Macmillan Press, 1976. MR 0411988 |
| . |
