| Title:
|
A bound on the $k$-domination number of a graph (English) |
| Author:
|
Volkmann, Lutz |
| Language:
|
English |
| Journal:
|
Czechoslovak Mathematical Journal |
| ISSN:
|
0011-4642 (print) |
| ISSN:
|
1572-9141 (online) |
| Volume:
|
60 |
| Issue:
|
1 |
| Year:
|
2010 |
| Pages:
|
77-83 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| Summary:
|
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. (English) |
| Keyword:
|
domination |
| Keyword:
|
$k$-domination number |
| Keyword:
|
$P_4$-free graphs |
| MSC:
|
05C35 |
| MSC:
|
05C69 |
| idZBL:
|
Zbl 1224.05385 |
| idMR:
|
MR2595071 |
| . |
| Date available:
|
2010-07-20T16:15:17Z |
| Last updated:
|
2020-07-03 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/140550 |
| . |
| Reference:
|
[1] Blidia, M., Chellali, M., Volkmann, L.: Bounds of the 2-domination number of graphs.Utilitas Math. 71 (2006), 209-216. Zbl 1113.05072, MR 2278833 |
| Reference:
|
[2] Caro, Y., Roditty, Y.: A note on the $k$-domination number of a graph.Int. J. Math. Sci. 13 (1990), 205-206. Zbl 0706.05033, MR 1038667, 10.1155/S016117129000031X |
| Reference:
|
[3] Chen, B., Zhou, S.: Upper bounds for $f$-domination number of graphs.Discrete Math. 185 (1998), 239-243. Zbl 0955.05077, MR 1614254, 10.1016/S0012-365X(97)00204-5 |
| Reference:
|
[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. Zbl 0664.05053, MR 0890244, 10.1002/jgt.3190090414 |
| Reference:
|
[5] Favaron, O., Hansberg, A., Volkmann, L.: On $k$-domination and minimum degree in graphs.J. Graph Theory 57 (2008), 33-40. MR 2370182, 10.1002/jgt.20279 |
| Reference:
|
[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. Zbl 0573.05049, MR 0812671 |
| Reference:
|
[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. Zbl 0573.05050, MR 0812672 |
| Reference:
|
[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. Zbl 0602.05043, MR 0833264, 10.1007/BF01848079 |
| Reference:
|
[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. Zbl 1179.05081, MR 2510244, 10.1016/j.dam.2008.10.011 |
| Reference:
|
[10] Ore, O.: Theory of Graphs.Amer. Math. Soc. Colloq. Publ. 38 (1962). Zbl 0105.35401, MR 0150753 |
| Reference:
|
[11] Payan, C., Xuong, N. H.: Domination-balanced graphs.J. Graph Theory 6 (1982), 23-32. Zbl 0489.05049, MR 0644738, 10.1002/jgt.3190060104 |
| Reference:
|
[12] Stracke, C., Volkmann, L.: A new domination conception.J. Graph Theory 17 (1993), 315-323. Zbl 0777.05074, MR 1220992, 10.1002/jgt.3190170306 |
| Reference:
|
[13] Zhou, S.: On $f$-domination number of a graph.Czech. Math. J. 46 (1996), 489-499. Zbl 0879.05037, MR 1408300 |
| Reference:
|
[14] Zhou, S.: Inequalities involving independence domination, $f$-domination, connected and total $f$-domination numbers.Czech. Math. J. 50 (2000), 321-330. MR 1761389, 10.1023/A:1022470802343 |
| . |
