On k‐domination and minimum degree in graphs
Odile Favaron, Adriana Hansberg, Lutz Volkmann · Journal of Graph Theory · 2007
Abstract A subset S of vertices of a graph G is k‐dominating if every vertex not in S has at least k neighbors in S. The k‐domination number $\gamma_k(G)$ is the minimum cardinality of a k‐dominating set of G. Different upper bounds on $\gamma_{k}(G)$ are known in terms of the order n and the minimum degree $\delta$ of G. In this self‐contained article, we present an Erdös‐type result, from which some of these bounds follow. In particular, we improve the bound $\gamma_{k}(G) \le (2k- \delta - 1)n/(2k -\delta)$ for $(\delta +3)/2 \le k \le \delta - 1$ , proved by Chen and Zhou in 1998. Furthermore, we characterize the extremal graphs in the inequality $\gamma_{k}(G) \le kn/(k +1)$ , if $k \le \delta$ , of Cockayne et al. This characterization generalizes that of graphs realizing $\gamma_1(G) = \gamma(G) = n/2$ . © 2007 Wiley Periodicals, Inc. J Graph Theory 57: 33–40, 2008