1. A bound on the $k$-domination number of a graph
- Creator:
- Volkmann, Lutz
- Format:
- bez média and svazek
- Type:
- model:article and TEXT
- Subject:
- domination, $k$-domination number, and $P_4$-free graphs
- Language:
- English
- Description:
- Let $G$ be a graph with vertex set $V(G)$, and let $k\ge 1$ be an integer. A subset $D \subseteq V(G)$ is called a {\it $k$-dominating set} if every vertex $v\in V(G)-D$ has at least $k$ neighbors in $D$. The $k$-domination number $\gamma _k(G)$ of $G$ is the minimum cardinality of a $k$-dominating set in $G$. If $G$ is a graph with minimum degree $\delta (G)\ge k+1$, then we prove that $$\gamma _{k+1}(G)\le \frac {|V(G)|+\gamma _k(G)}2.$$ In addition, we present a characterization of a special class of graphs attaining equality in this inequality.
- Rights:
- http://creativecommons.org/publicdomain/mark/1.0/ and policy:public