Proof of a conjecture on k-tuple domination in graphs

Guangjun Xu, Liying Kang, Erfang Shan, Hong Yan

Research output: Journal article publicationJournal articleAcademic researchpeer-review

10 Citations (Scopus)


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 languageEnglish
Pages (from-to)287-290
Number of pages4
JournalApplied Mathematics Letters
Issue number3
Publication statusPublished - 1 Mar 2008


  • Domination
  • k-tuple domination
  • Probabilistic method

ASJC Scopus subject areas

  • Computational Mechanics
  • Control and Systems Engineering
  • Applied Mathematics
  • Numerical Analysis

Cite this