International Journal of Mathematics and Mathematical Sciences
Volume 13 (1990), Issue 1, Pages 205-206
doi:10.1155/S016117129000031X
A note on the k-domination number of a graph
1Department of Mathematics, University of Haifa-Oranim, Geva 18915, Israel
2Department of Mathematics, Beit-Berl College and School of Mathematical Sciences, Tel-Aviv University, Israel
Received 30 December 1988; Revised 1 February 1989
Copyright © 1990 Y. Caro and Y. Roditty. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.
Abstract
The k-domination number of a graph G=G(V,E), γk(G), is the least cardinality of a set X⊂V such that any vertex in VX is adjacent to at least k vertices of X.
Extending a result of Cockayne, Gamble and Shepherd [4], we prove that if δ(G)≥n+1nk−1, n≥1, k≥1 then, γk(G)≤npn+1, where p is the order of G.