PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
2008 | 28 | 3 | 383-392
Tytuł artykułu

On locating and differentiating-total domination in trees

Treść / Zawartość
Warianty tytułu
Języki publikacji
EN
Abstrakty
EN
A total dominating set of a graph G = (V,E) with no isolated vertex is a set S ⊆ V such that every vertex is adjacent to a vertex in S. A total dominating set S of a graph G is a locating-total dominating set if for every pair of distinct vertices u and v in V-S, N(u)∩S ≠ N(v)∩S, and S is a differentiating-total dominating set if for every pair of distinct vertices u and v in V, N[u]∩S ≠ N[v] ∩S. Let $γₜ^L(G)$ and $γₜ^D(G)$ be the minimum cardinality of a locating-total dominating set and a differentiating-total dominating set of G, respectively. We show that for a nontrivial tree T of order n, with l leaves and s support vertices, $γₜ^L(T) ≥ max{2(n+l-s+1)/5,(n+2-s)/2}$, and for a tree of order n ≥ 3, $γₜ^D(T) ≥ 3(n+l-s+1)/7$, improving the lower bounds of Haynes, Henning and Howard. Moreover we characterize the trees satisfying $γₜ^L(T) = 2(n+l- s+1)/5$ or $γₜ^D(T) = 3(n+l-s+1)/7$.
Wydawca
Rocznik
Tom
28
Numer
3
Strony
383-392
Opis fizyczny
Daty
wydano
2008
otrzymano
2006-04-20
poprawiono
2008-03-14
zaakceptowano
2008-05-09
Twórcy
  • LAMDA-RO Laboratory, Department of Mathematics, University of Blida, B.P. 270, Blida, Algeria
Bibliografia
  • [1] M. Blidia, M. Chellali, F. Maffray, J. Moncel and A. Semri, Locating-domination and identifying codes in trees, Australasian J. Combin. 39 (2007) 219-232.
  • [2] M. Chellali and T.W. Haynes, A note on the total domination number of a tree, J. Combin. Math. Combin. Comput. 58 (2006) 189-193.
  • [3] J. Gimbel, B. van Gorden, M. Nicolescu, C. Umstead and N. Vaiana, Location with dominating sets, Congr. Numer. 151 (2001) 129-144.
  • [4] T.W. Haynes, M.A. Henning and J. Howard, Locating and total dominating sets in trees, Discrete Appl. Math. 154 (2006) 1293-1300, doi: 10.1016/j.dam.2006.01.002.
Typ dokumentu
Bibliografia
Identyfikatory
Identyfikator YADDA
bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1414
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ć.