View graph of relations

An inequality of Claude Berge's states that the domination number for a graph is at most its order minus its maximum valency. Conditions for equality are discussed both for the domination number and for the connected dominating number. The corresponding decision problems are proven to be co-NP-complete. Several domination theorems can be inproved by considering leaf densities. This has been done for theorems by Ore, Hartnell and Vestergaard. Both projects have publications pending. Cooperation with Anders Sune Pedersen
StatusCurrent
Period19-05-10 → …

ID: 18847