A bound on the $k$-domination number of a graph

@article{Volkmann2010,
abstract = {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 $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.},
author = {Volkmann, Lutz},
journal = {Czechoslovak Mathematical Journal},
keywords = {domination; $k$-domination number; $P_4$-free graphs; domination; -domination number; -free graph},
language = {eng},
number = {1},
pages = {77-83},
publisher = {Institute of Mathematics, Academy of Sciences of the Czech Republic},
title = {A bound on the $k$-domination number of a graph},
url = {http://eudml.org/doc/37989},
volume = {60},
year = {2010},
}

TY - JOUR
AU - Volkmann, Lutz
TI - A bound on the $k$-domination number of a graph
JO - Czechoslovak Mathematical Journal
PY - 2010
PB - Institute of Mathematics, Academy of Sciences of the Czech Republic
VL - 60
IS - 1
SP - 77
EP - 83
AB - 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 $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.
LA - eng
KW - domination; $k$-domination number; $P_4$-free graphs; domination; -domination number; -free graph
UR - http://eudml.org/doc/37989
ER -