show/hide this revision's text 6 added 5 characters in body; added 4 characters in body

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.

show/hide this revision's text 5 added 707 characters in body; added 7 characters in body

The

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 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 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.

show/hide this revision's text 4 added 106 characters in body

Doesn't this result require a particular degree sequence and so can't be used for an arbitrary graph

The 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 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 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). This is everything that has been done (as far as I know). Let me know if you learn more.

show/hide this revision's text 3 spelling
show/hide this revision's text 2 added 121 characters in body
show/hide this revision's text 1