Domination number of graphs with minimum degree five

We prove that for every graph $G$ on $n$ vertices and with minimum degree five, the domination number $γ(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.

No reviews yet.

No comments yet.