Geodesic
A bound on the $k$-domination number of a graph
Czechoslovak Mathematical Journal, Tome 60 (2010) no. 1, pp. 77-83 Cet article a éte moissonné depuis la source Czech Digital Mathematics Library

Voir la notice de l'article

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.
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},
     year = {2010},
     volume = {60},
     number = {1},
     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
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
%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/

[1] Blidia, M., Chellali, M., Volkmann, L.: Bounds of the 2-domination number of graphs. Utilitas Math. 71 (2006), 209-216. | MR | Zbl

[2] Caro, Y., Roditty, Y.: A note on the $k$-domination number of a graph. Int. J. Math. Sci. 13 (1990), 205-206. | DOI | MR | Zbl

[3] Chen, B., Zhou, S.: Upper bounds for $f$-domination number of graphs. Discrete Math. 185 (1998), 239-243. | DOI | MR | Zbl

[4] Cockayne, E. J., Gamble, B., Shepherd, B.: An upper bound for the $k$-domination number of a graph. J. Graph Theory 9 (1985), 533-534. | DOI | MR | Zbl

[5] Favaron, O., Hansberg, A., Volkmann, L.: On $k$-domination and minimum degree in graphs. J. Graph Theory 57 (2008), 33-40. | DOI | MR

[6] Fink, J. F., Jacobson, M. S.: $n$-domination in graphs. Graph Theory with Applications to Algorithms and Computer Science, John Wiley and Sons, New York (1985), 283-300. | MR | Zbl

[7] Fink, J. F., Jacobson, M. S.: On $n$-domination, $n$-dependence and forbidden subgraphs. Graph Theory with Applications to Algorithms and Computer Science, John Wiley and Sons, New York (1985), 301-311. | MR | Zbl

[8] Fink, J. F., Jacobson, M. S., Kinch, L. F., Roberts, J.: On graphs having domination number half their order. Period. Math. Hungar. 16 (1985), 287-293. | DOI | MR | Zbl

[9] Hansberg, A., Volkmann, L.: Upper bounds on the $k$-domination number and the $k$-Roman domination number. Discrete Appl. Math. 157 (2009), 1634-1639. | DOI | MR | Zbl

[10] Ore, O.: Theory of Graphs. Amer. Math. Soc. Colloq. Publ. 38 (1962). | MR | Zbl

[11] Payan, C., Xuong, N. H.: Domination-balanced graphs. J. Graph Theory 6 (1982), 23-32. | DOI | MR | Zbl

[12] Stracke, C., Volkmann, L.: A new domination conception. J. Graph Theory 17 (1993), 315-323. | DOI | MR | Zbl

[13] Zhou, S.: On $f$-domination number of a graph. Czech. Math. J. 46 (1996), 489-499. | MR | Zbl

[14] Zhou, S.: Inequalities involving independence domination, $f$-domination, connected and total $f$-domination numbers. Czech. Math. J. 50 (2000), 321-330. | DOI | MR