On locating and differentiating-total domination in trees
Discussiones Mathematicae. Graph Theory, Tome 28 (2008) no. 3, pp. 383-392
Voir la notice de l'article provenant de la source Library of Science
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) ≥ max2(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.
Keywords:
locating-total domination, differentiating-total domination, trees
@article{DMGT_2008_28_3_a0,
author = {Chellali, Mustapha},
title = {On locating and differentiating-total domination in trees},
journal = {Discussiones Mathematicae. Graph Theory},
pages = {383--392},
publisher = {mathdoc},
volume = {28},
number = {3},
year = {2008},
language = {en},
url = {http://geodesic.mathdoc.fr/item/DMGT_2008_28_3_a0/}
}
Chellali, Mustapha. On locating and differentiating-total domination in trees. Discussiones Mathematicae. Graph Theory, Tome 28 (2008) no. 3, pp. 383-392. http://geodesic.mathdoc.fr/item/DMGT_2008_28_3_a0/