Bounds on the k-domination number of a graph

Ermelinda Delaviña, Wayne Goddard, Michael A. Henning, Ryan Pepper, Emil R. Vaughan

Research output: Contribution to journalArticlepeer-review

21 Citations (Scopus)


The k-domination number of a graph is the cardinality of a smallest set of vertices such that every vertex not in the set is adjacent to at least k vertices of the set. We prove two bounds on the k-domination number of a graph, inspired by two conjectures of the computer program Graffiti.pc. In particular, we show that for any graph with minimum degree at least 2k-1, the k-domination number is at most the matching number.

Original languageEnglish
Pages (from-to)996-998
Number of pages3
JournalApplied Mathematics Letters
Issue number6
Publication statusPublished - Jun 2011


  • Graph
  • Independence number
  • Matching number
  • k-domination

ASJC Scopus subject areas

  • Applied Mathematics


Dive into the research topics of 'Bounds on the k-domination number of a graph'. Together they form a unique fingerprint.

Cite this