A generalised upper bound for the k-tuple domination number

Gagarin, Andrei; Zverovich, Vadim

Abstract

In this paper, we provide an upper bound for the k-tuple domination number that generalises known upper bounds for the double and triple domination numbers. We prove that for any graph G,γ× k (G) ≤ frac(ln (δ - k + 2) + ln (∑m = 1k - 1 (k - m) over(d, ^)m + ε{lunate}) + 1, δ - k + 2) n,where γ× k (G) is the k-tuple domination number; δ is the minimal degree; over(d, ^)m is the m-degree of G; ε{lunate} = 1 if k = 1 or 2 and ε{lunate} = - d if k ≥ 3; d is the average degree. © 2007 Elsevier B.V. All rights reserved.

• Journal Article Type: Article
• Publication Date: Mar 28, 2008
• Deposit Date: Nov 12, 2010
• Publicly Available Date: Nov 15, 2016
• Journal: Discrete Mathematics
• Print ISSN: 0012-365X
• Publisher: Elsevier
• Peer Reviewed: Peer Reviewed
• Volume: 308
• Issue: 5-6
• Pages: 880-885
• DOI: https://doi.org/10.1016/j.disc.2007.07.033
• Keywords: graph, domination
• Public URL: https://uwe-repository.worktribe.com/output/1018614
• Publisher URL: http://dx.doi.org/10.1016/j.disc.2007.07.033
• Contract Date: Nov 15, 2016