| Title:
|
Inequalities involving independence domination, $f$-domination, connected and total $f$-domination numbers (English) |
| Author:
|
Zhou, Sanming |
| Language:
|
English |
| Journal:
|
Czechoslovak Mathematical Journal |
| ISSN:
|
0011-4642 (print) |
| ISSN:
|
1572-9141 (online) |
| Volume:
|
50 |
| Issue:
|
2 |
| Year:
|
2000 |
| Pages:
|
321-330 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| 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. (English) |
| Keyword:
|
domination number |
| Keyword:
|
independence domination number |
| Keyword:
|
$f$-domination number |
| Keyword:
|
connected $f$-domination number |
| Keyword:
|
total $f$-domination number |
| MSC:
|
05C69 |
| MSC:
|
05C90 |
| MSC:
|
05C99 |
| idZBL:
|
Zbl 1045.05073 |
| idMR:
|
MR1761389 |
| . |
| Date available:
|
2009-09-24T10:32:56Z |
| Last updated:
|
2020-07-03 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/127571 |
| . |
| Reference:
|
[Allan-Laskar] R. B. Allan and R. Laskar: On domination and independent domination numbers of a graph.Discrete Math. 23 (1978), 73–76. MR 0523402, 10.1016/0012-365X(78)90105-X |
| Reference:
|
[Bollobas-Cockayne] B. Bollobás and E. J. Cockayne: Graph-theoretic parameters concerning domination, independence and irredundance.J. Graph Theory 3 (1979), 241–249. MR 0542545, 10.1002/jgt.3190030306 |
| Reference:
|
[Cockayne-Dawes-Hedetniemi] E. J. Cockayne, R. M. Dawes and S. T. Hedetniemi: Total domination in graphs.Networks 10 (1980), 211–219. MR 0584887, 10.1002/net.3230100304 |
| Reference:
|
[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 |
| Reference:
|
[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 |
| Reference:
|
[Graver-Watkins] J. E. Graver and M. E. Watkins: Combinatorics with Emphasis on the Theory of Graphs.Springer-Verlag, New York, 1977. MR 0505525 |
| Reference:
|
[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 |
| Reference:
|
[Stracke-Volkmann] C. Stracke and L. Volkmann: A new domination conception.J. Graph Theory 17 (1993), 315–323. MR 1220992 |
| Reference:
|
[Weinstein] J. M. Weinstein: On the number of disjoint edges in a graph.Canad. J. Math. 15 (1963), 106–111. Zbl 0112.14803, MR 0153002, 10.4153/CJM-1963-012-2 |
| Reference:
|
[Zhou] S. M. Zhou: On $f$-domination number of a graph.Czechoslovak Math. J. 46(121) (1996), 489–499. Zbl 0879.05037, MR 1408300 |
| Reference:
|
[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. |
| Reference:
|
[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. |
| . |
