zbMATH — the first resource for mathematics

Domination in bipartite graphs and in their complements. (English) Zbl 1021.05074
Summary: The domatic number of a graph \(G\) and of its complement \(\overline G\) were studied by J. E. Dunbar, T. W. Haynes and M. A. Henning. They suggested four open problems. We solve the following ones:
Characterize the bipartite graphs \(G\) with \(d(G) = d(\overline G)\). Further, we present a partial solution to the problem: Is it true that if \(G\) is a graph satisfying \(d(G) = d(\overline G)\), then \(\gamma (G) = \gamma (\overline G)\)? Finally, we prove an existence theorem concerning the total domatic number of a graph and of its complement.
05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
Full Text: DOI EuDML
[1] E. J. Cockayne and S. T. Hedetniemi: Towards the theory of domination in graphs. Networks 7 (1977), 247-261. · Zbl 0384.05051
[2] E. J. Cockayne, R. M. Dawes and S. T. Hedetniemi: Total domination in graphs. Networks 10 (1980), 211-219. · Zbl 0447.05039
[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. · Zbl 0902.05039
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.