Improved upper bounds on the domination number of graphs with minimum degree at least five

An algorithmic upper bound on the domination number $γ$ of graphs in terms of the order $n$ and the minimum degree $δ$ is proved. It is demonstrated that the bound improves best previous bounds for any $5\le δ\le 50$. In particular, for $δ=5$, Xing et al.\ proved in 2006 that $γ\le 5n/14 < 0.3572 n$. This bound is improved to $0.3440 n$. For $δ=6$, Clark et al.\ in 1998 established $γ<0.3377 n$, while Biró et al. recently improved it to $γ<0.3340 n$. Here the bound is further improved to $γ< 0.3159 n$. For $δ=7$, the best earlier bound $0.3 088 n$ is improved to $γ< 0.2927 n$.

No reviews yet.

No comments yet.