Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

I have a graph $G$ whose minimum vertex degree is $\delta=7$. I am seeking an upper bound on the domination number $\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), 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!

share|improve this question
    
Actually, if the graph has nice structure, the bound can be improved. Let me know if you are still interested in this. –  Felix Goldberg Apr 2 at 23:54
add comment

1 Answer

up vote 4 down vote accepted

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

n[1+ln(k+1)]/(k+1)

by Arnautov 1974, and Payan 1975 but the articles were written in Russian and French (resp.). 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 Y. Caro and Y. Roditty, On the vertex-independence number and star decomposition of graphs, Ars Combin. 20 (1985), 167-180. Next comes the result you mentioned 0.311844 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 On the domination number of Hamiltonian graphs with minimum degree six by Xing, Hattingh, and Plummer Applied Math. Letters 21 (2008) 1037-1040 for the most recent paper published on this topic.

A short proof of the result of Arnautov and Payan can be found in Intro to graph Theory by Douglas West 2nd Ed page 117 which uses the greedy algorithm (by Alon). Discussion 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 Stocker 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) fo 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 is this helps. The result is by Duckworth and Wormald entitled On the Independent Domination Number of Random Regular Graphs Combinatorics, Probability and Computing submitted in 2003.

share|improve this answer
    
Thank you, these are useful references to me! –  Joseph O'Rourke Apr 23 '12 at 14:29
    
There is also a nice probabilistic proof of the Amautov & Payan result in Lesniak & Chartrand. Or at East was in the 3rd edition. –  Felix Goldberg Apr 25 '12 at 21:03
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.