Abstract
Let G = (V, E) be a graph and NG [v] the closed neighborhood of a vertex v in G. For k ∈ N, the minimum cardinality of a set D ⊆ V with | NG [v] ∩ D | ≥ k for all v ∈ V is the k-tuple domination number γ× k (G) of G. In this note we prove the following conjecture of 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]: If k ∈ N and G = (V, E) is a graph of order n and minimum degree δ ≥ k, then γ× k (G) ≤ frac(n, δ + 2 - k) (ln (δ + 2 - k) + ln (under(∑, v ∈ V) (frac(dG (v) + 1, k - 1))) - ln (n) + 1) .
Original language | English |
---|---|
Pages (from-to) | 287-290 |
Number of pages | 4 |
Journal | Applied Mathematics Letters |
Volume | 21 |
Issue number | 3 |
DOIs | |
Publication status | Published - 1 Mar 2008 |
Keywords
- Domination
- k-tuple domination
- Probabilistic method
ASJC Scopus subject areas
- Computational Mechanics
- Control and Systems Engineering
- Applied Mathematics
- Numerical Analysis