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

Abstract

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

References in corpus (1)

• On the game domination number of graphs with given minimum degree