The k-tuple domination number revisited

Zverovich, Vadim

Abstract

The following fundamental result for the domination number γ (G) of a graph G was proved by Alon and Spencer, Arnautov, Lovász and Payan: γ (G) ≤ frac(ln (δ + 1) + 1, δ + 1) n, where n is the order and δ is the minimum degree of vertices of G. 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 k-domination number and the k-tuple domination number, Appl. Math. Lett. 20 (2007) 98-102], who also posed the interesting conjecture on the k-tuple domination number: for any graph G with δ ≥ k - 1, γ× k (G) ≤ frac(ln (δ - k + 2) + ln (over(d, ̂)k - 1 + over(d, ̂)k - 2) + 1, δ - k + 2) n, where over(d, ̂)m = ∑i = 1n ((di; m)) / n is the m-degree of G. 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 k-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. © 2007 Elsevier Ltd. All rights reserved.

• Journal Article Type: Article
• Publication Date: Oct 1, 2008
• Deposit Date: Nov 16, 2010
• Publicly Available Date: Nov 15, 2016
• Journal: Applied Mathematics Letters
• Print ISSN: 0893-9659
• Publisher: Elsevier
• Peer Reviewed: Peer Reviewed
• Volume: 21
• Issue: 10
• Pages: 1005-1011
• DOI: https://doi.org/10.1016/j.aml.2007.10.016
• Keywords: graphs, domination number, double domination, triple domination, k-tuple domination
• Public URL: https://uwe-repository.worktribe.com/output/1022885
• Publisher URL: http://dx.doi.org/10.1016/j.aml.2007.10.016
• Contract Date: Nov 15, 2016