On k-domination and minimum degree in graphs

✍ Scribed by Odile Favaron; Adriana Hansberg; Lutz Volkmann

• Publisher: John Wiley and Sons
• Year: 2007
• Tongue: English
• Weight: 129 KB
• Volume: 57
• Category: Article
• ISSN: 0364-9024
• DOI: 10.1002/jgt.20279

✦ Synopsis

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