International Journal of Mathematics and Mathematical Sciences
Volume 13 (1990), Issue 1, Pages 205-206

A note on the k-domination number of a graph

Y. Caro1 and Y. Roditty2

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.


The k-domination number of a graph G=G(V,E), γk(G), is the least cardinality of a set XV 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+1nk1, n1, k1 then, γk(G)npn+1, where p is the order of G.