Article
Full entry |
PDF
(0.2 MB)
Feedback
PDF
(0.2 MB)
Feedback
Keywords:
bipartite graph; complement of a graph; domatic number
bipartite graph; complement of a graph; domatic number
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.
References:
[1] E. J. Cockayne and S. T. Hedetniemi: Towards the theory of domination in graphs. Networks 7 (1977), 247–261. DOI 10.1002/net.3230070305 | MR 0483788
[2] E. J. Cockayne, R. M. Dawes and S. T. Hedetniemi: Total domination in graphs. Networks 10 (1980), 211–219. DOI 10.1002/net.3230100304 | MR 0584887
[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
Search
Partner of
