The upper bound on k-tuple domination numbers of graphs
Journal
European Journal of Combinatorics
Journal Volume
29
Journal Issue
5
Pages
1333-1336
Date Issued
2008
Author(s)
Abstract
In a graph G, a vertex is said to dominate itself and all vertices adjacent to it. For a positive integer k, the k-tuple domination number γ× k (G) of G is the minimum size of a subset D of V (G) such that every vertex in G is dominated by at least k vertices in D. To generalize/improve known upper bounds for the k-tuple domination number, this paper establishes that for any positive integer k and any graph G of n vertices and minimum degree δ, γ× k (G) ≤ frac(ln (δ - k + 2) + ln over(d, ̃)k - 1 + 1, δ - k + 2) n, where over(d, ̃)m = frac(1, n) ∑i = 1n fenced(frac(di + 1, m)) with di the degree of the ith vertex of G. © 2007 Elsevier Ltd. All rights reserved.
Type
journal article