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!
$\begingroup$
$\endgroup$
1
asked Feb 21, 2012 at 14:01
-
$\begingroup$ Actually, if the graph has nice structure, the bound can be improved. Let me know if you are still interested in this. $\endgroup$– Felix GoldbergApr 2, 2014 at 23:54
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
1
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. 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, Appl. Math. Lett. 21, No. 10, 1037-1040 (2008), ZBL1160.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, 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, Comb. Probab. Comput. 15, No. 4, 513-522 (2006), ZBL1121.05084.
- 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.
- Payan, C., Sur le nombre d’absorption d’un graphe simple, Cah. Cent. Étud. Rech. Opér. 17, 307-317 (1975), ZBL0341.05126.
- Kostochka, A. V.; Stocker, Christopher, A new bound on the domination number of connected cubic graphs, Sib. Èlektron. Mat. Izv. 6, 465-504 (2009), ZBL1299.05252.
-
$\begingroup$ There is also a nice probabilistic proof of the Amautov & Payan result in Lesniak & Chartrand. Or at East was in the 3rd edition. $\endgroup$ Apr 25, 2012 at 21:03
$\begingroup$
$\endgroup$
See this article, it provides the best bound till date:
Bujtás, Csilla; Klavžar, Sandi, Improved upper bounds on the domination number of graphs with minimum degree at least five, Graphs Comb. 32, No. 2, 511-519 (2016). ZBL1339.05280.
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 \leq \delta \leq 50$. In particular, for $\delta =5$, Xing et al. (Graphs Comb. 22:127–143, 2006) proved that $\gamma \leq 5n/14 < 0.3572n$. This bound is improved to $0.3440 n$. For $\delta=6$, Clark et al. (Congr. Numer. 132:99–123, 1998) established $\gamma < 0.3377n$, while Biró et al. (Bull. Inst. Comb. Appl. 64:73–83, 2012) 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$.
