Article
Full entry |
PDF
(0.3 MB)
Feedback
PDF
(0.3 MB)
Feedback
Keywords:
domination number; independence domination number; $f$-domination number; connected $f$-domination number; total $f$-domination number
domination number; independence domination number; $f$-domination number; connected $f$-domination number; total $f$-domination number
Summary:
Let $f$ be an integer-valued function defined on the vertex set $V(G)$ of a graph $G$. A subset $D$ of $V(G)$ is an $f$-dominating set if each vertex $x$ outside $D$ is adjacent to at least $f(x)$ vertices in $D$. The minimum number of vertices in an $f$-dominating set is defined to be the $f$-domination number, denoted by $\gamma _{f}(G)$. In a similar way one can define the connected and total $f$-domination numbers $\gamma _{c, f}(G)$ and $\gamma _{t, f}(G)$. If $f(x) = 1$ for all vertices $x$, then these are the ordinary domination number, connected domination number and total domination number of $G$, respectively. In this paper we prove some inequalities involving $\gamma _{f}(G), \gamma _{c, f}(G), \gamma _{t, f}(G)$ and the independence domination number $i(G)$. In particular, several known results are generalized.
References:
[Allan-Laskar] R. B. Allan and R. Laskar: On domination and independent domination numbers of a graph. Discrete Math. 23 (1978), 73–76. DOI 10.1016/0012-365X(78)90105-X | MR 0523402
[Bollobas-Cockayne] B. Bollobás and E. J. Cockayne: Graph-theoretic parameters concerning domination, independence and irredundance. J. Graph Theory 3 (1979), 241–249. DOI 10.1002/jgt.3190030306 | MR 0542545
[Cockayne-Dawes-Hedetniemi] E. J. Cockayne, R. M. Dawes and S. T. Hedetniemi: Total domination in graphs. Networks 10 (1980), 211–219. DOI 10.1002/net.3230100304 | MR 0584887
[Fink-Jacobson-1] J. F. Fink and M. S. Jacobson: $n$-domination in graphs. Graph Theory with Applications to Algorithms and Computer Science. John Wiley & Sons, New York, 1985, pp. 283–300. MR 0812671
[Fink-Jacobson-2] J. F. Fink and M. S. Jacobson: On $n$-domination, $n$-dependence and forbidden subgraphs. Graph Theory with Applications to Algorithms and Computer Science. John Wiley & Sons, New York, 1985, pp. 301–311. MR 0812672
[Graver-Watkins] J. E. Graver and M. E. Watkins: Combinatorics with Emphasis on the Theory of Graphs. Springer-Verlag, New York, 1977. MR 0505525
[Hedetniemi-Hedetniemi-Laskar] S. Hedetniemi, S. Hedetniemi and R. Laskar: Domination in trees: models and algorithms. Graph Theory with Applications to Algorithms and Computer Science. John Wiley & Sons, New York, 1985, pp. 423–442. MR 0812681
[Stracke-Volkmann] C. Stracke and L. Volkmann: A new domination conception. J. Graph Theory 17 (1993), 315–323. MR 1220992
[Weinstein] J. M. Weinstein: On the number of disjoint edges in a graph. Canad. J. Math. 15 (1963), 106–111. DOI 10.4153/CJM-1963-012-2 | MR 0153002 | Zbl 0112.14803
[Zhou] S. M. Zhou: On $f$-domination number of a graph. Czechoslovak Math. J. 46(121) (1996), 489–499. MR 1408300 | Zbl 0879.05037
[Zhou-Zhang] S. M. Zhou and J. Y. Zhang: Invariants concerning $f$-domination in graphs. Combinatorics and Graph Theory ’95. World Scientific, River Edge, NJ, 1999.
[Zhou-1] S. M. Zhou and X. N. Yue: Gallai-type equalities for $f$-domination and connected $f$-domination numbers. Graph Theory Notes of New York XXIX (1995), 30–32.
Search
Partner of
