Geodesic
Inequalities involving independence domination, $f$-domination, connected and total $f$-domination numbers
Czechoslovak Mathematical Journal, Tome 50 (2000) no. 2, pp. 321-330 Cet article a éte moissonné depuis la source Czech Digital Mathematics Library

Voir la notice de l'article

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.
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.
Classification : 05C69, 05C90, 05C99
Keywords: domination number; independence domination number; $f$-domination number; connected $f$-domination number; total $f$-domination number 
@article{CMJ_2000_50_2_a6,
     author = {Zhou, Sanming},
     title = {Inequalities involving independence domination, $f$-domination, connected and total $f$-domination numbers},
     journal = {Czechoslovak Mathematical Journal},
     pages = {321--330},
     year = {2000},
     volume = {50},
     number = {2},
     mrnumber = {1761389},
     zbl = {1045.05073},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/CMJ_2000_50_2_a6/}
}
TY  - JOUR
AU  - Zhou, Sanming
TI  - Inequalities involving independence domination, $f$-domination, connected and total $f$-domination numbers
JO  - Czechoslovak Mathematical Journal
PY  - 2000
SP  - 321
EP  - 330
VL  - 50
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/CMJ_2000_50_2_a6/
LA  - en
ID  - CMJ_2000_50_2_a6
ER  - 
%0 Journal Article
%A Zhou, Sanming
%T Inequalities involving independence domination, $f$-domination, connected and total $f$-domination numbers
%J Czechoslovak Mathematical Journal
%D 2000
%P 321-330
%V 50
%N 2
%U http://geodesic.mathdoc.fr/item/CMJ_2000_50_2_a6/
%G en
%F CMJ_2000_50_2_a6
Zhou, Sanming. Inequalities involving independence domination, $f$-domination, connected and total $f$-domination numbers. Czechoslovak Mathematical Journal, Tome 50 (2000) no. 2, pp. 321-330. http://geodesic.mathdoc.fr/item/CMJ_2000_50_2_a6/

[Allan-Laskar] R. B. Allan and R. Laskar: On domination and independent domination numbers of a graph. Discrete Math. 23 (1978), 73–76. | DOI | MR

[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 | MR

[Cockayne-Dawes-Hedetniemi] E. J. Cockayne, R. M. Dawes and S. T. Hedetniemi: Total domination in graphs. Networks 10 (1980), 211–219. | DOI | MR

[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

[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

[Graver-Watkins] J. E. Graver and M. E. Watkins: Combinatorics with Emphasis on the Theory of Graphs. Springer-Verlag, New York, 1977. | MR

[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

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

[Weinstein] J. M. Weinstein: On the number of disjoint edges in a graph. Canad. J. Math. 15 (1963), 106–111. | DOI | MR | Zbl

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

[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.