1. Domination in bipartite graphs and in their complements
- Creator:
- Zelinka, Bohdan
- Format:
- bez média and svazek
- Type:
- model:article and TEXT
- Subject:
- bipartite graph, complement of a graph, and domatic number
- Language:
- English
- Description:
- 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.
- Rights:
- http://creativecommons.org/publicdomain/mark/1.0/ and policy:public