×

zbMATH — the first resource for mathematics

Total restrained domination in graphs with minimum degree two. (English) Zbl 1226.05195
Summary: We continue the study of total restrained domination in graphs, a concept introduced by J. A. Telle and A. Proskurowksi [“Algorithms for vertex partitioning problems on partial \(k\)-trees,” SIAM J. Discrete Math. 10, No. 4, 529–550 (1997; Zbl 0885.68118)] as a vertex partitioning problem. A set \(S\) of vertices in a graph \(G=(V,E)\) is a total restrained dominating set of \(G\) if every vertex is adjacent to a vertex in \(S\) and every vertex of \(V\backslash S\) is adjacent to a vertex in \(V\backslash S\).
The minimum cardinality of a total restrained dominating set of \(G\) is the total restrained domination number of \(G\), denoted by \(\gamma _{\text{tr}}(G)\). Let \(G\) be a connected graph of order \(n\) with minimum degree at least 2 and with maximum degree \(\varDelta \) where \(\varDelta \leqslant n-2\). We prove that if \(n\geqslant \)4, then \(\gamma _{\text{tr}}(G)\leqslant n-\frac{\varDelta}{2}-1\) and this bound is sharp. If we restrict \(G\) to a bipartite graph with \(\Delta \geqslant \)3, then we improve this bound by showing that \(\gamma _{\text{tr}}(G)\leqslant n-\frac{2}{3}\varDelta -\frac 2 9 \sqrt{3\varDelta -8} - \frac 7 9\) and that this bound is sharp.

MSC:
05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] 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
[2] Berge, C., Theory of graphs and its applications, (1962), Methuen London · Zbl 0097.38903
[3] Cockayne, E.J.; Dawes, R.M.; Hedetniemi, S.T., Total domination in graphs, Networks, 10, 211-219, (1980) · Zbl 0447.05039
[4] P. Dankelmann, D. Day, J.H. Hattingh, M.A. Henning, L.R. Markus, H.C. Swart, On equality in an upper bound for the restrained and total domination numbers of a graph, Discrete Math., in press, doi:10.1016/j.disc.2007.03.003. · Zbl 1138.05049
[5] Domke, G.S.; Hattingh, J.H.; Hedetniemi, S.T.; Laskar, R.C.; Markus, L.R., Restrained domination, Discrete math., 203, 61-69, (1999) · Zbl 1114.05303
[6] Domke, G.S.; Hattingh, J.H.; Henning, M.A.; Markus, L.R., Restrained domination in graphs with minimum degree two, J. combin. math. combin. comput., 35, 239-254, (2000) · Zbl 0971.05087
[7] Domke, G.S.; Hattingh, J.H.; Henning, M.A.; Markus, L.R., Restrained domination in trees, Discrete math., 211, 1-9, (2000) · Zbl 0947.05057
[8] Favaron, O.; Henning, M.A., Upper total domination in claw-free graphs, J. graph theory, 44, 148-158, (2003) · Zbl 1028.05078
[9] 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
[10] Favaron, O.; Mynhardt, C.M., On equality in an upper bound for domination parameters of graphs, J. graph theory, 24, 221-231, (1997) · Zbl 0872.05025
[11] Hattingh, J.H.; Henning, M.A., Characterisations of trees with equal domination parameters, J. graph theory, 34, 142-153, (2000) · Zbl 0947.05065
[12] J.H. Hattingh, E. Jonck, E.J. Joubert, A.R. Plummer, Total restrained domination in trees, Discrete Math., in press, doi:10.1016/j.disc.2006.09.014. · Zbl 1132.05044
[13] Haynes, T.W.; Hedetniemi, S.T.; Slater, P.J., Fundamentals of domination in graphs, (1998), Marcel Dekker New York · Zbl 0890.05002
[14] T.W. Haynes, S.T. Hedetniemi, P.J. Slater (Eds.), Domination in Graphs: Advanced Topics, Marcel Dekker, New York, 1998. · Zbl 0883.00011
[15] Henning, M.A., Graphs with large restrained domination number, 16th british combinatorial conference (London, 1997), Discrete math., 197/198, 415-429, (1999)
[16] Henning, M.A., Graphs with large total domination number, J. graph theory, 35, 1, 21-45, (2000) · Zbl 0959.05089
[17] Ma, D.-X.; Chen, X.-G.; Sun, L., On total restrained domination in graphs, Czechoslovak math. J., 55, 165-173, (2005) · Zbl 1081.05086
[18] Telle, J.A.; Proskurowski, A., Algorithms for vertex partitioning problems on partial \(k\)-trees, SIAM J. discrete math., 10, 529-550, (1997) · Zbl 0885.68118
[19] Zelinka, B., Remarks on restrained domination and total restrained domination in graphs, Czechoslovak math. J., 55, 393-396, (2005) · Zbl 1081.05050
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.