Domination number of graphs with minimum degree five

Abstract

We prove that for every graph $G$ on $n$ vertices and with minimum degree five, the domination number $\gamma (G)$ cannot exceed $n/3$. The proof combines an algorithmic approach and the discharging method. Using the same technique, we provide a shorter proof for the known upper bound $4n/11$ on the domination number of graphs of minimum degree four.

arXiv comment17 pages