PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
2016 | 36 | 1 | 71-93
Tytuł artykułu

Vertices Contained In All Or In No Minimum Semitotal Dominating Set Of A Tree

Treść / Zawartość
Warianty tytułu
Języki publikacji
EN
Abstrakty
EN
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.
Słowa kluczowe
Wydawca
Rocznik
Tom
36
Numer
1
Strony
71-93
Opis fizyczny
Daty
wydano
2016-02-01
otrzymano
2014-12-18
poprawiono
2015-04-13
zaakceptowano
2015-04-13
online
2016-01-19
Twórcy
  • Department of Pure and Applied Mathematics University of Johannesburg Auckland Park, 2006, South Africa, mahenning@uj.ac.za
  • Department of Pure and Applied Mathematics University of Johannesburg Auckland Park, 2006, South Africa, alister.marcon@gmail.com
Bibliografia
  • [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.
  • [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]
  • [3] W. Goddard, M.A. Henning and C.A. McPillan, Semitotal domination in graphs, Util. Math. 94 (2014) 67–81.
  • [4] T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Fundamentals of Domination in Graphs (Marcel Dekker, Inc. New York, 1998).
  • [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]
  • [7] M.A. Henning and A.J. Marcon, Semitotal domination in graphs: Partition and algorithmic results, Util. Math., to appear.
  • [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]
  • [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]
Typ dokumentu
Bibliografia
Identyfikatory
Identyfikator YADDA
bwmeta1.element.doi-10_7151_dmgt_1844
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.