Geodesic
A bound on the $k$-domination number of a graph
Czechoslovak Mathematical Journal, Tome 60 (2010) no. 1, pp. 77-83

Voir la notice de l'article provenant de la source Czech Digital Mathematics Library

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.
Classification : 05C35, 05C69
Keywords: domination; $k$-domination number; $P_4$-free graphs 
@article{CMJ_2010__60_1_a4,
     author = {Volkmann, Lutz},
     title = {A bound on the $k$-domination number of a graph},
     journal = {Czechoslovak Mathematical Journal},
     pages = {77--83},
     publisher = {mathdoc},
     volume = {60},
     number = {1},
     year = {2010},
     mrnumber = {2595071},
     zbl = {1224.05385},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/CMJ_2010__60_1_a4/}
}
TY  - JOUR
AU  - Volkmann, Lutz
TI  - A bound on the $k$-domination number of a graph
JO  - Czechoslovak Mathematical Journal
PY  - 2010
SP  - 77
EP  - 83
VL  - 60
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/CMJ_2010__60_1_a4/
LA  - en
ID  - CMJ_2010__60_1_a4
ER  - 
%0 Journal Article
%A Volkmann, Lutz
%T A bound on the $k$-domination number of a graph
%J Czechoslovak Mathematical Journal
%D 2010
%P 77-83
%V 60
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/CMJ_2010__60_1_a4/
%G en
%F CMJ_2010__60_1_a4
Volkmann, Lutz. A bound on the $k$-domination number of a graph. Czechoslovak Mathematical Journal, Tome 60 (2010) no. 1, pp. 77-83. http://geodesic.mathdoc.fr/item/CMJ_2010__60_1_a4/