Article
Full entry |
PDF
(0.2 MB)
Feedback
PDF
(0.2 MB)
Feedback
Keywords:
domination; $k$-domination number; $P_4$-free graphs
domination; $k$-domination number; $P_4$-free graphs
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.
References:
[1] Blidia, M., Chellali, M., Volkmann, L.: Bounds of the 2-domination number of graphs. Utilitas Math. 71 (2006), 209-216. MR 2278833 | Zbl 1113.05072
[2] Caro, Y., Roditty, Y.: A note on the $k$-domination number of a graph. Int. J. Math. Sci. 13 (1990), 205-206. DOI 10.1155/S016117129000031X | MR 1038667 | Zbl 0706.05033
[3] Chen, B., Zhou, S.: Upper bounds for $f$-domination number of graphs. Discrete Math. 185 (1998), 239-243. DOI 10.1016/S0012-365X(97)00204-5 | MR 1614254 | Zbl 0955.05077
[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 10.1002/jgt.3190090414 | MR 0890244 | Zbl 0664.05053
[5] Favaron, O., Hansberg, A., Volkmann, L.: On $k$-domination and minimum degree in graphs. J. Graph Theory 57 (2008), 33-40. DOI 10.1002/jgt.20279 | MR 2370182
[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 0812671 | Zbl 0573.05049
[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 0812672 | Zbl 0573.05050
[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 10.1007/BF01848079 | MR 0833264 | Zbl 0602.05043
[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 10.1016/j.dam.2008.10.011 | MR 2510244 | Zbl 1179.05081
[10] Ore, O.: Theory of Graphs. Amer. Math. Soc. Colloq. Publ. 38 (1962). MR 0150753 | Zbl 0105.35401
[11] Payan, C., Xuong, N. H.: Domination-balanced graphs. J. Graph Theory 6 (1982), 23-32. DOI 10.1002/jgt.3190060104 | MR 0644738 | Zbl 0489.05049
[12] Stracke, C., Volkmann, L.: A new domination conception. J. Graph Theory 17 (1993), 315-323. DOI 10.1002/jgt.3190170306 | MR 1220992 | Zbl 0777.05074
[13] Zhou, S.: On $f$-domination number of a graph. Czech. Math. J. 46 (1996), 489-499. MR 1408300 | Zbl 0879.05037
[14] Zhou, S.: Inequalities involving independence domination, $f$-domination, connected and total $f$-domination numbers. Czech. Math. J. 50 (2000), 321-330. DOI 10.1023/A:1022470802343 | MR 1761389
Search
Partner of
