Vertices Contained In All Or In No Minimum Semitotal Dominating Set Of A Tree
Michael A. Henning ; Alister J. Marcon
Discussiones Mathematicae Graph Theory, Tome 36 (2016), p. 71-93 / Harvested from The Polish Digital Mathematics Library
Access to full text
Full (PDF)

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, γ(G), and the total domination number, γ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, γt2(G), is the minimum cardinality of a semitotal dominating set of G. We observe that γ(G) ≤ γt2(G) ≤ γt(G). We characterize the set of vertices that are contained in all, or in no minimum semitotal dominating set of a tree.

Publié le : 2016-01-01
EUDML-ID : urn:eudml:doc:276976 
@article{bwmeta1.element.doi-10_7151_dmgt_1844,
     author = {Michael A. Henning and Alister J. Marcon},
     title = {Vertices Contained In All Or In No Minimum Semitotal Dominating Set Of A Tree},
     journal = {Discussiones Mathematicae Graph Theory},
     volume = {36},
     year = {2016},
     pages = {71-93},
     zbl = {1329.05232},
     language = {en},
     url = {http://dml.mathdoc.fr/item/bwmeta1.element.doi-10_7151_dmgt_1844}
}

Michael A. Henning; Alister J. Marcon. Vertices Contained In All Or In No Minimum Semitotal Dominating Set Of A Tree. Discussiones Mathematicae Graph Theory, Tome 36 (2016) pp. 71-93. http://gdmltest.u-ga.fr/item/bwmeta1.element.doi-10_7151_dmgt_1844/

[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[Crossref] | 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[Crossref][WoS]

[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[Crossref] | 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[Crossref] | Zbl 1122.05071

[9] M.A. Henning and A. Yeo, Total domination in graphs (Springer Monographs in Mathematics, 2013).

[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[Crossref] | Zbl 0931.05063