Journal of Graph Theory · 1985 · 54 citations · 0 references
Natural SciencesComputer ScienceMathematicsCombinatoricsComputational GeometryTheory Of ComputationEnumerative CombinatoricsGraph AlgorithmsGraph TheoryCardinality EstimationDominating SetsUpper Bound Computation
Abstract 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).