Vertices contained in all or in no minimum semitotal dominating set of a tree. (English) Zbl 1329.05232
Summary: Let \(G\) be a graph with no isolated vertex. In this paper, we study a parameter that is squeezed between arguably the two most important domination parameters; namely, the domination number, \(\gamma(G)\), and the total domination number, \(\gamma_t(G)\). A set \(S\) of vertices in a graph \(G\) is a semitotal dominating set of \(G\) if it is a dominating set of \(G\) and every vertex in \(S\) is within distance 2 of another vertex of \(S\). The semitotal domination number, \(\gamma_{t2}(G)\), is the minimum cardinality of a semitotal dominating set of \(G\). We observe that \(\gamma(G) \leq \gamma_{t2}(G) \leq \gamma_t(G)\). We characterize the set of vertices that are contained in all, or in no minimum semitotal dominating set of a tree.
MSC:
| 05C69 | Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) |
References:
| [1] | M. Blidia, M. Chellali and S. Khelifi, Vertices belonging to all or no minimum double dominating sets in trees, AKCE Int. J. Graphs. Comb. 2 (2005) 1-9.; · Zbl 1076.05058 |
| [2] | E.J. Cockayne, M.A. Henning and C.M. Mynhardt, Vertices contained in all or in no minimum total dominating set of a tree, Discrete Math. 260 (2003) 37-44. doi:10.1016/S0012-365X(02)00447-8; · Zbl 1013.05054 |
| [3] | W. Goddard, M.A. Henning and C.A. McPillan, Semitotal domination in graphs, Util. Math. 94 (2014) 67-81.; · Zbl 1300.05220 |
| [4] | T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Fundamentals of Domination in Graphs (Marcel Dekker, Inc. New York, 1998).; · Zbl 0890.05002 |
| [5] | M.A. Henning, Recent results on total domination in graphs: A survey, Discrete Math. 309 (2009) 32-63. doi:10.1016/j.disc.2007.12.044; · Zbl 1219.05121 |
| [6] | M.A. Henning and A.J. Marcon, On matching and semitotal domination in graphs, Discrete Math. 324 (2014) 13-18. doi:10.1016/j.disc.2014.01.021; · Zbl 1284.05196 |
| [7] | M.A. Henning and A.J. Marcon, Semitotal domination in graphs: Partition and algorithmic results, Util. Math., to appear.; · Zbl 1284.05196 |
| [8] | M.A. Henning and M.D. Plummer, Vertices contained in all or in no minimum paired-dominating set of a tree, J. Comb. Optim. 10 (2005) 283-294. doi:10.1007/s10878-005-4107-3; · Zbl 1122.05071 |
| [9] | M.A. Henning and A. Yeo, Total domination in graphs (Springer Monographs in Mathematics, 2013).; · Zbl 1408.05002 |
| [10] | C.M. Mynhardt, Vertices contained in every minimum dominating set of a tree, J. Graph Theory 31 (1999) 163-177. doi:10.1002/(SICI)1097-0118(199907)31:3〈163::AID-JGT2〉3.0.CO;2-T; · Zbl 0931.05063 |
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
