appropriate upper bound on dominating number of graphs Denote the dominating number of a graph $G$ by $\gamma(G)$. I have found a number of upper bounds on $\gamma(G)$. For example, in Theorem 1.2.2 of Alon & Spencer's book, named "The Probabilistic Method", for a graph $G$ with minimal degree $d$, we have: $\gamma(G)\leq n\cdot\frac{1+ln(d+1)}{d+1}$.
Unfortunately, this bound is not suitable for my work. I want to know if a better upper bound exists.
 A: It is quiet logically that this result is not very accurate. In this bound is used from minimum degree of vertices of the graphs. Minimum degree of the graph is a local property. With knowing the minimum degree of a graph, we don't have any information about other vertices or edges of a graph. For example, for all trees with $n$ vertices, we have $d=1$ and so this bound gives the same bound for all of them. Therefore, you must recognize the properties of your graph. Is your graph a bipartite graph, a chordal graph, a regular graph and etc.
A: As far as I know, $\gamma(G)\leq kn/(3k-1)$ is the most famous conjectured upper bound on the domination number of a graph $G$ with $\delta(G)\geq k$.
In the book 
T.W. Haynes, S.T. Hedetniemi, and P.J. Slater, Fundamentals of domination in graphs, Marcel Dekker, New York, 1998.
the authors conjectured that 
$$\gamma(G)\leq kn/(3k-1),$$
for all graph $G$ with $\delta(G)\geq k$.
For $\delta(G)\geq7$, Caro and Rodity, in the paper 
Y. Caro, Y. Roditty, A note on the $k$-domination number of a graph, Internat. J. Math. Sci. 13 (1990), 205--206.
gave a better upper bound.
On the other hand, in the paper 
H. Liu and L. Sun, On domination number of $4$-regular graphs, Czechoslovak Math. J. 54 (2004), 889--898.
the authors showed that the conjecture is true for $4$-regular graphs.
Moreover, in the paper
Hua-Ming Xing, Liang Sun, and Xue-Gang Chen, Czechoslovak Math. J. 56 (2006), 1049--1061.
the authors showed that the conjecture is true for $5$-regular graphs.
So, the problem is open for graphs with $\delta(G)=6$.
