Article
Full entry |
PDF
(0.2 MB)
Feedback
PDF
(0.2 MB)
Feedback
Keywords:
minus domination; total domination; minus total domination
minus domination; total domination; minus total domination
Summary:
A three-valued function $f\: V\rightarrow \{-1,0,1\}$ defined on the vertices of a graph $G=(V,E)$ is a minus total dominating function (MTDF) if the sum of its function values over any open neighborhood is at least one. That is, for every $v\in V$, $f(N(v))\ge 1$, where $N(v)$ consists of every vertex adjacent to $v$. The weight of an MTDF is $f(V)=\sum f(v)$, over all vertices $v\in V$. The minus total domination number of a graph $G$, denoted $\gamma _t^{-}(G)$, equals the minimum weight of an MTDF of $G$. In this paper, we discuss some properties of minus total domination on a graph $G$ and obtain a few lower bounds for $\gamma _t^{-}(G)$.
References:
[1] Allan, R. B., Laskar, R. C., Hedetniemi, S. T.: A note on total domination. Discrete Math. 49 (1984), 7-13. DOI 10.1016/0012-365X(84)90145-6 | MR 0737612 | Zbl 0576.05028
[2] Archdeacon, D., Ellis-Monaghan, J., Fisher, D., al., et: Some remarks on domination. Journal of Graph Theory 46 (2004), 207-210. DOI 10.1002/jgt.20000 | MR 2063370 | Zbl 1041.05057
[3] Arumugam, S., Thuraiswamy, A.: Total domination in graphs. Ars Combin. 43 (1996), 89-92. MR 1415977 | Zbl 0881.05063
[4] Cockayne, E. J., Dawes, R. M., Hedetniemi, S. T.: Total domination in graphs. Networks 10 (1980), 211-219. DOI 10.1002/net.3230100304 | MR 0584887 | Zbl 0447.05039
[5] Dunbar, J. E., Goddard, W., Hedetniemi, S. T., Henning, M. A., McRae, A. A.: The algorithmic complexity of minus domination in graphs. Discrete Appl. Math. 68 (1996), 73-84. DOI 10.1016/0166-218X(95)00056-W | MR 1393310 | Zbl 0848.05041
[6] Dunbar, J. E., Hedetniemi, S. T., Henning, M. A., McRae, A. A.: Minus domination in regular graphs. Discrete Math. 149 (1996), 311-312. DOI 10.1016/0012-365X(94)00329-H | MR 1375119 | Zbl 0843.05059
[7] Dunbar, J. E., Hedetniemi, S. T., Henning, M. A., McRae, A. A.: Minus domination in graphs. Discrete Math. 199 (1999), 35-47. MR 1675909 | Zbl 0928.05046
[8] Favaron, O., Henning, M. A., Mynhart, C. M., al., et: Total domination in graphs with minimum degree three. Journal of Graph Theory 32 (1999), 303-310.
[9] Harris, L., Hattingh, J. H.: The algorithmic complexity of certain functional variations of total domination in graphs. Australas. Journal of Combin. 29 (2004), 143-156. MR 2037343 | Zbl 1084.05049
[10] Haynes, T. W., Hedetniemi, S. T., Slater, P. J.: Fundamentals of domination in graphs. New York, Marcel Dekker (1998). MR 1605684 | Zbl 0890.05002
[11] Henning, M. A.: Graphs with large total domination number. Journal of Graph Theory 35 (2000), 21-45. DOI 10.1002/1097-0118(200009)35:1<21::AID-JGT3>3.0.CO;2-F | MR 1775793 | Zbl 0959.05089
[12] Henning, M. A.: Signed total domination in graphs. Discrete Math. 278 (2004), 109-125. DOI 10.1016/j.disc.2003.06.002 | MR 2035392 | Zbl 1036.05035
[13] Kang, L. Y., Kim, H. K., Sohn, M. Y.: Minus domination number in $k$-partite graphs. Discrete Math. 227 (2004), 295-300. DOI 10.1016/j.disc.2003.07.008 | MR 2033739 | Zbl 1033.05077
[14] Xing, H. M., Sun, L., Chen, X. G.: On signed total domination in graphs. Journal of Beijing Institute of Technology 12 (2003), 319-321. MR 2007855
[15] Xing, H. M., Sun, L., Chen, X. G.: On a generalization of signed total dominating functions of graphs. Ars Combin. 77 (2005), 205-215. MR 2180845 | Zbl 1164.05426
[16] Zelinka, B.: Signed total domination number of a graph. Czech. Math. J. 51 (2001), 225-229. DOI 10.1023/A:1013782511179 | MR 1844306 | Zbl 0977.05096
Search
Partner of
