| Title:
|
Minus total domination in graphs (English) |
| Author:
|
Xing, Hua-Ming |
| Author:
|
Liu, Hai-Long |
| Language:
|
English |
| Journal:
|
Czechoslovak Mathematical Journal |
| ISSN:
|
0011-4642 (print) |
| ISSN:
|
1572-9141 (online) |
| Volume:
|
59 |
| Issue:
|
4 |
| Year:
|
2009 |
| Pages:
|
861-870 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| 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)$. (English) |
| Keyword:
|
minus domination |
| Keyword:
|
total domination |
| Keyword:
|
minus total domination |
| MSC:
|
05C69 |
| idZBL:
|
Zbl 1224.05387 |
| idMR:
|
MR2563563 |
| . |
| Date available:
|
2010-07-20T15:45:13Z |
| Last updated:
|
2020-07-03 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/140521 |
| . |
| Reference:
|
[1] Allan, R. B., Laskar, R. C., Hedetniemi, S. T.: A note on total domination.Discrete Math. 49 (1984), 7-13. Zbl 0576.05028, MR 0737612, 10.1016/0012-365X(84)90145-6 |
| Reference:
|
[2] Archdeacon, D., Ellis-Monaghan, J., Fisher, D., al., et: Some remarks on domination.Journal of Graph Theory 46 (2004), 207-210. Zbl 1041.05057, MR 2063370, 10.1002/jgt.20000 |
| Reference:
|
[3] Arumugam, S., Thuraiswamy, A.: Total domination in graphs.Ars Combin. 43 (1996), 89-92. Zbl 0881.05063, MR 1415977 |
| Reference:
|
[4] Cockayne, E. J., Dawes, R. M., Hedetniemi, S. T.: Total domination in graphs.Networks 10 (1980), 211-219. Zbl 0447.05039, MR 0584887, 10.1002/net.3230100304 |
| Reference:
|
[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. Zbl 0848.05041, MR 1393310, 10.1016/0166-218X(95)00056-W |
| Reference:
|
[6] Dunbar, J. E., Hedetniemi, S. T., Henning, M. A., McRae, A. A.: Minus domination in regular graphs.Discrete Math. 149 (1996), 311-312. Zbl 0843.05059, MR 1375119, 10.1016/0012-365X(94)00329-H |
| Reference:
|
[7] Dunbar, J. E., Hedetniemi, S. T., Henning, M. A., McRae, A. A.: Minus domination in graphs.Discrete Math. 199 (1999), 35-47. Zbl 0928.05046, MR 1675909 |
| Reference:
|
[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. |
| Reference:
|
[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. Zbl 1084.05049, MR 2037343 |
| Reference:
|
[10] Haynes, T. W., Hedetniemi, S. T., Slater, P. J.: Fundamentals of domination in graphs.New York, Marcel Dekker (1998). Zbl 0890.05002, MR 1605684 |
| Reference:
|
[11] Henning, M. A.: Graphs with large total domination number.Journal of Graph Theory 35 (2000), 21-45. Zbl 0959.05089, MR 1775793, 10.1002/1097-0118(200009)35:1<21::AID-JGT3>3.0.CO;2-F |
| Reference:
|
[12] Henning, M. A.: Signed total domination in graphs.Discrete Math. 278 (2004), 109-125. Zbl 1036.05035, MR 2035392, 10.1016/j.disc.2003.06.002 |
| Reference:
|
[13] Kang, L. Y., Kim, H. K., Sohn, M. Y.: Minus domination number in $k$-partite graphs.Discrete Math. 227 (2004), 295-300. Zbl 1033.05077, MR 2033739, 10.1016/j.disc.2003.07.008 |
| Reference:
|
[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 |
| Reference:
|
[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. Zbl 1164.05426, MR 2180845 |
| Reference:
|
[16] Zelinka, B.: Signed total domination number of a graph.Czech. Math. J. 51 (2001), 225-229. Zbl 0977.05096, MR 1844306, 10.1023/A:1013782511179 |
| . |
