I have a graph $G$ whose minimum vertex degree is $\delta=7$.
I am seeking an upper bound on the [domination number](http://en.wikipedia.org/wiki/Dominating_set) $\gamma(G)$
in terms of the number of vertices $n$ of $G$.
I found a paper by
Edwin Clark, Boris Shekhtman, Stephen Suen, and David Fisher, 
"Upper bounds for the domination number of a graph," *Congressus 
Numerantium*, 132:99–124, 1998 ([CiteSeer link](http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.54.6194)),
that implies a bound of about $0.31 n$ (more precisely, $(18286568 / 58640175)n$).
I was hoping for a smaller upper bound. Perhaps there have been advances since that paper?
Any pointers to relevant literature would be much appreciated. Thanks!



Bound on graph domination number when min degree is 7
I believe the complete history is as follows. For an arbitrary graph with $n$ vertices and minimum degree $k$, the result has been shown to be at most
$$
\frac{n[1+\ln(k+1)]}{k+1}
$$
by Arnautov1 (1974) and Payan2 (1975), but the articles were written in Russian and French, respectively. For $k=7$, this gives a bound of $0.384930n$. In 1985, Caro and Roditty improved this bound slightly to $0.325283n$ when $k=7$. For this second result, see *Caro, Y.; Roditty, Y.*, On the vertex-independence number and star decomposition of graphs, Ars Comb. 20, 167-180 (1985), [ZBL0623.05031](https://zbmath.org/?q=an:0623.05031). Next comes the result you mentioned: $0.311844n$ in 1996 (not 1998). So, unfortunately, I think the answer is that your bound is the best known at this time. See also the discussion at the beginning of *Xing, Hua-Ming; Hattingh, Johannes H.; Plummer, Andrew R.*, [**On the domination number of Hamiltonian graphs with minimum degree six**](http://dx.doi.org/10.1016/j.aml.2007.10.023), Appl. Math. Lett. 21, No. 10, 1037-1040 (2008), [ZBL1160.05326](https://zbmath.org/?q=an:1160.05326) for the most recent paper published on this topic.


A short proof of the result of Arnautov and Payan can be found in
*West, Douglas B.*, Introduction to graph theory, New Delhi: Prentice-Hall of India (ISBN 81-203-2142-1). 608 p. (2005), [ZBL1121.05304](https://zbmath.org/?q=an:1121.05304), on page 117, which uses the greedy algorithm (by Alon). Discussions are also found in papers for $k=2,3,4,5,6$ by various authors (I'm guessing this may not be of use to you but these cover some history). There is a new paper by Kostochka and Stocker3 for cubic graphs ($5n/14$) which indicates that some authors are still working on this problem. This is everything that has been done (as far as I know). Let me know if you learn more.


Another approach would be to use the independent domination number $i(G)$ since $\gamma(G) \le i(G)$ for any graph $G$. I think the most recent result here is $0.18329n$, *but* this is only for a $7$-regular graph.
Not sure if this helps. The result is *Duckworth, W.; Wormald, N. C.*, [**On the independent domination number of random regular graphs**](http://dx.doi.org/10.1017/S0963548305007431), Comb. Probab. Comput. 15, No. 4, 513-522 (2006), [ZBL1121.05084](https://zbmath.org/?q=an:1121.05084).




---


1. *Arnautov, V. I.*, Abschätzung der äußeren Stabilitätszahl eines Graphen mit Hilfe des Minimalgrades der Ecken, Prikl. Mat. Programm. 11, 3-8 (1974), [ZBL0297.05131](https://zbmath.org/?q=an:0297.05131).
2. *Payan, C.*, Sur le nombre d’absorption d’un graphe simple, Cah. Cent. Étud. Rech. Opér. 17, 307-317 (1975), [ZBL0341.05126](https://zbmath.org/?q=an:0341.05126).
3. *Kostochka, A. V.; Stocker, Christopher*, [**A new bound on the domination number of connected cubic graphs**](http://semr.math.nsc.ru/v6/p465-504.pdf), Sib. Èlektron. Mat. Izv. 6, 465-504 (2009), [ZBL1299.05252](https://zbmath.org/?q=an:1299.05252).


