×

zbMATH — the first resource for mathematics

A survey of selected recent results on total domination in graphs. (English) Zbl 1219.05121
Summary: A set \(S\) of vertices in a graph \(G\) is a total dominating set of \(G\) if every vertex of \(G\) is adjacent to some vertex in \(S\). In this paper, we offer a survey of selected recent results on total domination in graphs.

MSC:
05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
05-02 Research exposition (monographs, survey articles) pertaining to combinatorics
Software:
Graffiti.pc
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Adhar, G.S.; Peng, S., Parallel algorithms for finding connected, independent and total domination in interval graphs, (), 85-90
[2] Alon, N., Transversal number of uniform hypergraphs, Graphs combin., 6, 1-4, (1990) · Zbl 0742.05065
[3] Archdeacon, D.; Ellis-Monaghan, J.; Fischer, D.; Froncek, D.; Lam, P.C.B.; Seager, S.; Wei, B.; Yuster, R., Some remarks on domination, J. graph theory, 46, 207-210, (2004) · Zbl 1041.05057
[4] Arnborg, S.; Lagergren, J.; Seese, D., Easy problems for tree-decomposable graphs, J. algorithms, 12, 308-340, (1991) · Zbl 0734.68073
[5] Bertossi, A.A., Total domination in interval graphs, Inform. process. lett., 23, 131-134, (1986) · Zbl 0604.05032
[6] Bertossi, A.A.; Gori, A., Total domination and irredundance in weighted interval graphs, SIAM J. discrete math., 1, 317-327, (1988) · Zbl 0648.05041
[7] Bertossi, A.A.; Moretti, S., Parallel algorithms on circular-arc graphs, Inform. process. lett., 33, 275-281, (1990) · Zbl 0696.68049
[8] Bollobás, B.; Cockayne, E.J., Graph-theoretic parameters concerning domination, independence, and irredundance, J. graph theory, 3, 241-249, (1979) · Zbl 0418.05049
[9] Brandstädt, A.; Kratsch, D., On domination problems on permutation and other graphs, Theoret. comput. sci., 54, 181-198, (1987) · Zbl 0641.68100
[10] Brigham, R.C.; Carrington, J.R.; Vitray, R.P., Connected graphs with maximum total domination number, J. combin. comput. combin. math., 34, 81-96, (2000) · Zbl 0958.05100
[11] Broere, I.; Dorfling, M.; Goddard, W.; Hattingh, J.H.; Henning, M.A.; Ungerer, E., Augmenting trees to have two disjoint total dominating sets, Bull. inst. combin. appl., 42, 12-18, (2004) · Zbl 1057.05061
[12] Calkin, N.; Dankelmann, P., The domatic number of regular graphs, Ars combin., 73, 247-255, (2004) · Zbl 1073.05046
[13] Chang, G.J., Labeling algorithms for domination problems in Sun-free chordal graphs, Discrete appl. math., 22, 21-34, (1988) · Zbl 0667.05054
[14] Chang, M.S., Efficient algorithms for the domination problems on interval and circular-arc graphs, SIAM J. comput., 27, 1671-1694, (1998) · Zbl 0911.05051
[15] Chang, M.S.; Wu, S.C.; Chang, G.J.; Yeh, H.G., Domination in distance-hereditary graphs, Discrete appl. math., 116, 103-113, (2002) · Zbl 0991.05077
[16] M. Chellali, O. Favaron, T.W. Haynes, D. Raber, Ratios of some domination parameters in trees Discrete Mathematics, Discrete Math., Available online 27 August 2007 · Zbl 1167.05307
[17] Chvátal, V.; McDiarmid, C., Small transversals in hypergraphs, Combinatorica, 12, 19-26, (1992) · Zbl 0776.05080
[18] Cockayne, E.J.; Dawes, R.M.; Hedetniemi, S.T., Total domination in graphs, Networks, 10, 211-219, (1980) · Zbl 0447.05039
[19] Cockayne, E.; Henning, M.A.; Mynhardt, C.M., Vertices contained in all or in no minimum total dominating set of a tree, Discrete math., 260, 37-44, (2003) · Zbl 1013.05054
[20] Corneil, D.G.; Stewart, L., Dominating sets in perfect graphs, Discrete math., 86, 145-164, (1990) · Zbl 0746.05066
[21] Dankelmann, P.; Domke, G.S.; Goddard, W.; Grobler, P.; Hattingh, J.H.; Swart, H.C., Maximum sizes of graphs with given domination parameters, Discrete math., 281, 137-148, (2004) · Zbl 1044.05053
[22] Dorbec, P.; Gravier, S.; Klavzˆar, S.; Ŝpacapan, S., Some results on total domination in direct products of graphs, Discuss. math. graph theory, 26, 103-112, (2006) · Zbl 1103.05059
[23] Dorbec, P.; Henning, M.A.; McCoy, J., Upper total domination versus upper paired-domination, Quaest. math., 30, 1-12, (2007) · Zbl 1134.05071
[24] P. Dorbec, M.A. Henning, D.F. Rall, On the upper total domination number of Cartesian products of graphs, J. Combin. Optim (in press) · Zbl 1157.05042
[25] E. DeLaViña, Q. Liu, R. Pepper, B. Waller, D.B. West, Some conjectures of Graffiti.pc on total domination, manuscript, 2007 · Zbl 1134.05070
[26] Dorfling, M.; Goddard, W.; Hattingh, J.H; Henning, M.A., Augmenting a graph of minimum degree 2 to have two disjoint total dominating sets, Discrete math., 300, 82-90, (2005) · Zbl 1073.05047
[27] Dorfling, M.; Goddard, W.; Henning, M.A., Domination in planar graphs with small diameter II, Ars combin., 78, 237-255, (2006) · Zbl 1164.05418
[28] Dorfling, M.; Goddard, W.; Henning, M.A.; Mynhardt, C.M., Construction of trees and graphs with equal domination parameters, Discrete math., 306, 2647-2654, (2006) · Zbl 1104.05053
[29] M. El-Zahar, S. Gravier, A. Klobucar, On the total domination number of cross products of graphs, Discrete Math., in press (doi:10.1016/j.disc.2007.04.034) · Zbl 1168.05344
[30] Feige, U.; Halldórsson, M.M.; Kortsarz, G.; Srinivasan, A., Approximating the domatic number, SIAM J. comput., 32, 172-195, (2002) · Zbl 1021.05072
[31] Favaron, O.; Henning, M.A., Upper total domination in claw-free graphs, J. graph theory, 44, 148-158, (2003) · Zbl 1028.05078
[32] Favaron, O.; Henning, M.A., Paired domination in claw-free cubic graphs, Graphs combin., 20, 447-456, (2004) · Zbl 1054.05074
[33] Favaron, O.; Henning, M.A.; Mynhardt, C.M.; Puech, J., Total domination in graphs with minimum degree three, J. graph theory, 34, 1, 9-19, (2000) · Zbl 0945.05047
[34] O. Favaron, M.A. Henning, Total domination in claw-free graphs with minimum degree two, Discrete Math., in press (doi:10.1016/j.disc.2007.06.024) · Zbl 1158.05044
[35] O. Favaron, M.A. Henning, Bounds on total domination in claw-free cubic graphs, Discrete Math., in press (doi:10.1016/j.disc.2007.07.007) · Zbl 1190.05089
[36] Garey, M.R.; Johnson, D.S., Computers and intractability: A guide to the theory of NP-completeness, (1979), W.H. Freeman San Francisco · Zbl 0411.68039
[37] Goddard, W.; Henning, M.A., Domination in planar graphs with small diameter, J. graph theory, 40, 1-25, (2002) · Zbl 0997.05072
[38] Goddard, W.; Haynes, T.W.; Henning, M.A.; van der Merwe, L.C., The diameter of total domination vertex critical graphs, Discrete math., 286, 255-261, (2004) · Zbl 1055.05113
[39] Gravier, S., Total domination number of grid graphs, Discrete appl. math., 121, 119-128, (2002) · Zbl 0995.05109
[40] Heggernes, P.; Telle, J.A., Partitioning graphs into generalized dominating sets, Nordic J. comput., 5, 128-142, (1998) · Zbl 0905.68100
[41] Hanson, D.; Wang, P., A note on extremal total domination edge critical graphs, Util. math., 63, 89-96, (2003) · Zbl 1035.05063
[42] B. Hartnell, D.F. Rall, Domination in Cartesian products: Vizing’s Conjecture, In [44] pp. 163-189 · Zbl 0890.05035
[43] ()
[44] ()
[45] Haynes, T.W.; Henning, M.A., Trees with unique minimum total dominating sets, Discuss. math. graph theory, 22, 233-246, (2002) · Zbl 1031.05095
[46] T.W. Haynes, M.A. Henning, Upper bounds on the total domination number, Ars Combin. (in press) · Zbl 1224.05368
[47] S.T. Hedetniemi, A.A. McRae, D.A. Parks, Complexity results. See Chapter 9 in [44] · Zbl 0891.68050
[48] Henning, M.A., Graphs with large total domination number, J. graph theory, 35, 1, 21-45, (2000) · Zbl 0959.05089
[49] Henning, M.A., Trees with large total domination number, Util. math., 60, 99-106, (2001) · Zbl 1011.05045
[50] Henning, M.A., A linear vizing-like relation relating the size and total domination number of a graph, J. graph theory, 49, 285-290, (2005) · Zbl 1075.05068
[51] M.A. Henning, L. Kang, E. Shan, A Yeo, On matching and total domination in graphs, Discrete Math., in press (doi:10.1016/j.disc.2006.10.024) · Zbl 1145.05042
[52] Henning, M.A.; Rall, D.F., On the total domination number of Cartesian products of graph, Graphs combin., 21, 63-69, (2005) · Zbl 1062.05109
[53] M.A. Henning, J. Southey, A note on graphs with disjoint dominating and total dominating sets, Ars Combin. (in press) · Zbl 1224.05370
[54] M.A. Henning, A. Yeo, Hypergraphs with large transversal number and with edge sizes at least three, manuscript (2005) · Zbl 1211.05091
[55] Henning, M.A.; Yeo, A., A transition from total domination in graphs to transversals in hypergraphs, Quaest. math., 30, 417-436, (2007) · Zbl 1140.05315
[56] Henning, M.A.; Yeo, A., A new upper bound on the total domination number of a graph, Electronic J. combin., 14, (2007), #R65 · Zbl 1158.05046
[57] M.A. Henning, A. Yeo, Total domination in 2-connected graphs and in graphs with no induced 6-cycles, manuscript (2007) · Zbl 1189.05131
[58] M.A. Henning, A. Yeo, Total domination in graphs with given girth, manuscript (2007) · Zbl 1180.05080
[59] P. Tung Ho, A note on the total domination number, Util. Math. (in press) · Zbl 1161.05056
[60] Imrich, W.; Klavžar, S., Product graphs: structure and recognition, (2000), John Wiley & Sons New York
[61] Keil, J.M., Total domination in interval graphs, Inform. process. lett., 22, 171-174, (1986) · Zbl 0595.05063
[62] Keil, J.M., The complexity of domination problems in circle graphs, Discrete appl. math., 42, 51-63, (1993) · Zbl 0786.05079
[63] Kratsch, D.; Stewart, L., Domination on cocomparability graphs, SIAM J. discrete math., 6, 400-417, (1993) · Zbl 0780.05032
[64] Kratsch, D.; Stewart, L., Total domination and transformation, Inform. process. lett., 63, 167-170, (1997) · Zbl 1337.68133
[65] D. Kratsch, Algorithms, See Chapter 8 in [44]
[66] Kratsch, D., Domination and total domination on asteroidal triple-free graphs, Proceedings of the 5th Twente workshop on graphs and combinatorial optimization (Enschede, 1997), Discrete appl. math., 99, 111-123, (2000) · Zbl 0943.05063
[67] Lam, P.C.B.; Wei, B., On the total domination number of graphs, Utilitas math., 72, 223-240, (2007) · Zbl 1120.05065
[68] R.C. Laskar, J. Pfaff, Domination and irredundance in split graphs, Technical Report 430, Clemson University, Dept. Math. Sciences. 1983
[69] Laskar, R.C.; Pfaff, J.; Hedetniemi, S.M.; Hedetniemi, S.T., On the algorithmic complexity of total domination, SIAM J. algebraic discrete methods, 5, 420-425, (1984) · Zbl 0576.68056
[70] MacGillivray, G.; Seyffarth, K., Domination numbers of planar graphs, J. graph theory, 22, 213-229, (1996) · Zbl 0854.05062
[71] A.A. McRae, Generalizing NP-completeness proofs for bipartite and chordal graphs. Ph.D. Thesis, Clemson Univ., 1994
[72] Meir, A.; Moon, J.W., Relations between packing and covering numbers of a tree, Pacific J. math., 61, 225-233, (1975) · Zbl 0315.05102
[73] Mitchell, S.L.; Cockayne, E.J.; Hedetniemi, S.T., Linear algorithms on recursive representations of trees, J. comput. syst. sci., 18, 76-85, (1979) · Zbl 0398.68008
[74] Nowakowski, R.J.; Rall, D.F., Associative graph products and their independence, domination and coloring numbers, Discuss. math. graph theory, 16, 53-79, (1996) · Zbl 0865.05071
[75] J. Pfaff, R.C. Laskar, S.T. Hedetniemi, NP-completeness of total and connected domination and irredundance for bipartite graphs, Technical Report 428, Clemson University, Dept. Math. Sciences, 1983
[76] Rao, A.; Pandu Rangan, C., Optimal parallel algorithms on circular-arc graphs, Inform. process. lett., 33, 147-156, (1989) · Zbl 0688.68046
[77] Rall, D.F., Total domination in categorical products of graphs, Discuss. math. graph theory, 25, 35-44, (2005) · Zbl 1074.05068
[78] Ramalingam, G.; Rangan, C.P., Total domination in interval graphs revisited, Inform. process. lett., 27, 17-21, (1988) · Zbl 0662.68069
[79] Sanchis, L.A., Relating the size of a connected graph to its total and restricted domination numbers, Discrete math., 283, 205-216, (2004) · Zbl 1042.05075
[80] Shan, E.; Kang, L.; Henning, M.A., Erratum to: A linear vizing-like relation relating the size and total domination number of a graph, J. graph theory, 54, 350-353, (2007) · Zbl 1115.05065
[81] Sumner, D.P.; Blitch, P., Domination critical graphs, J. combin. theory ser. B, 34, 65-76, (1983) · Zbl 0512.05055
[82] Sun, L., An upper bound for the total domination number, J. Beijing inst. technol., 4, 111-114, (1995) · Zbl 0845.05058
[83] Telle, J.A., Complexity of domination-type problems in graphs, Nordic J. comput., 1, 157-171, (1994)
[84] S. Thomassé, A. Yeo, Total domination of graphs and small transversals of hypergraphs, Combinatorica (in press)
[85] A. Yeo, Improved bound on the total domination in graphs with minimum degree four, manuscript, 2005
[86] Yeo, A., Relationships between total domination, order, size, and maximum degree of graphs, J. graph theory, 55, 325-337, (2007) · Zbl 1123.05070
[87] Tuza, Z., Covering all cliques of a graph, Discrete math., 86, 117-126, (1990) · Zbl 0744.05040
[88] L.C. van der Merwe, Total domination edge critical graphs. Ph.D. Thesis, University of South Africa, 1999. Advisors: C. M. Mynhardt and T. W. Haynes · Zbl 0918.05069
[89] van der Merwe, L.C.; Loizeaux, M.A., 4-critical graphs with maximum diameter, Jcmcc, 60, 65-80, (2007) · Zbl 1123.05072
[90] van der Merwe, L.C.; Mynhardt, C.M.; Haynes, T.W., Total domination edge critical graphs, Util. math., 54, 229-240, (1998) · Zbl 0918.05069
[91] van der Merwe, L.C.; Mynhardt, C.M.; Haynes, T.W., 3-domination critical graphs with arbitrary independent domination numbers, Bull. inst. combin. appl., 27, 85-88, (1999) · Zbl 0944.05074
[92] van der Merwe, L.C.; Mynhardt, C.M.; Haynes, T.W., Total domination edge critical graphs with maximum diameter, Discuss. math. graph theory, 21, 187-205, (2001) · Zbl 1007.05077
[93] Vizing, V.G., A bound on the external stability number of a graph, Dokl. akad. nauk SSSR, 164, 729-731, (1965) · Zbl 0136.44703
[94] Zelinka, B., Total domatic number and degrees of vertices of a graph, Math. slovaca, 39, 7-11, (1989) · Zbl 0688.05066
[95] Zelinka, B., Domatic numbers of graphs and their variants: A survey, (), 351-377 · Zbl 0894.05026
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.