Abstract
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 language | English |
---|---|
Pages (from-to) | 996-998 |
Number of pages | 3 |
Journal | Applied Mathematics Letters |
Volume | 24 |
Issue number | 6 |
DOIs | |
Publication status | Published - Jun 2011 |
Keywords
- Graph
- Independence number
- Matching number
- k-domination
ASJC Scopus subject areas
- Applied Mathematics