Premium
An upper bound for the k ‐domination number of a graph
Author(s) -
Cockayne E. J.,
Gamble B.,
Shepherd B.
Publication year - 1985
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.3190090414
Subject(s) - combinatorics , mathematics , vertex (graph theory) , domination analysis , graph , bound graph , upper and lower bounds , discrete mathematics , graph power , line graph , mathematical analysis
The k ‐domination number of a graph G , γ k ( G ), is the least cardinality of a set U of verticies such that any other vertex is adjacent to at least k vertices of U. We prove that if each vertex has degree at least k , then γ k ( G ) ≤ kp /( k + 1).