| Title:
|
Domination in bipartite graphs and in their complements (English) |
| Author:
|
Zelinka, Bohdan |
| Language:
|
English |
| Journal:
|
Czechoslovak Mathematical Journal |
| ISSN:
|
0011-4642 (print) |
| ISSN:
|
1572-9141 (online) |
| Volume:
|
53 |
| Issue:
|
2 |
| Year:
|
2003 |
| Pages:
|
241-247 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| Summary:
|
The domatic numbers of a graph $G$ and of its complement $\bar{G}$ were studied by J. E. Dunbar, T. W. Haynes and M. A. Henning. They suggested four open problems. We will solve the following ones: Characterize bipartite graphs $G$ having $d(G) = d(\bar{G})$. Further, we will present a partial solution to the problem: Is it true that if $G$ is a graph satisfying $d(G) = d(\bar{G})$, then $\gamma (G) = \gamma (\bar{G})$? Finally, we prove an existence theorem concerning the total domatic number of a graph and of its complement. (English) |
| Keyword:
|
bipartite graph |
| Keyword:
|
complement of a graph |
| Keyword:
|
domatic number |
| MSC:
|
05C69 |
| idZBL:
|
Zbl 1021.05074 |
| idMR:
|
MR1983448 |
| . |
| Date available:
|
2009-09-24T11:01:02Z |
| Last updated:
|
2020-07-03 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/127796 |
| . |
| Reference:
|
[1] E. J. Cockayne and S. T. Hedetniemi: Towards the theory of domination in graphs.Networks 7 (1977), 247–261. MR 0483788, 10.1002/net.3230070305 |
| Reference:
|
[2] E. J. Cockayne, R. M. Dawes and S. T. Hedetniemi: Total domination in graphs.Networks 10 (1980), 211–219. MR 0584887, 10.1002/net.3230100304 |
| Reference:
|
[3] J. E. Dunbar, T. W. Haynes and M. A. Henning: The domatic number of a graph and its complement.Congr. Numer. 8126 (1997), 53–63. MR 1604974 |
| . |
