The k-tuple domination number revisited

The following fundamental result for the domination number γ(G)γ(G) of a graph GG was proved by Alon and Spencer, Arnautov, Lovász and Payan: γ(G)≤ln(δ+1)+1δ+1n, where nn is the order and δδ is the minimum degree of vertices of GG. A similar upper bound for the double domination number was found by Harant and Henning [J. Harant, M.A. Henning, On double domination in graphs, Discuss. Math. Graph Theory 25 (2005) 29–34], and for the triple domination number by Rautenbach and Volkmann [D. Rautenbach, L. Volkmann, New bounds on the kk-domination number and the kk-tuple domination number, Appl. Math. Lett. 20 (2007) 98–102], who also posed the interesting conjecture on the kk-tuple domination number: for any graph GG with δ≥k−1δ≥k−1, γ×k(G)≤ln(δ−k+2)+ln(d̂k−1+d̂k−2)+1δ−k+2n, where d̂m=∑i=1n(dim)/n is the mm-degree of GG. This conjecture, if true, would generalize all the mentioned upper bounds and improve an upper bound proved in [A. Gagarin, V. Zverovich, A generalised upper bound for the kk-tuple domination number, Discrete Math. (2007), in press (doi:10.1016/j.disc.2007.07.033)].In this paper, we prove the Rautenbach–Volkmann conjecture.