On locating and differentiating-total domination in trees

Mustapha Chellali. "On locating and differentiating-total domination in trees." Discussiones Mathematicae Graph Theory 28.3 (2008): 383-392. <http://eudml.org/doc/270636>.

@article{MustaphaChellali2008,
abstract = {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$.},
author = {Mustapha Chellali},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {locating-total domination; differentiating-total domination; trees},
language = {eng},
number = {3},
pages = {383-392},
title = {On locating and differentiating-total domination in trees},
url = {http://eudml.org/doc/270636},
volume = {28},
year = {2008},
}

TY - JOUR
AU - Mustapha Chellali
TI - On locating and differentiating-total domination in trees
JO - Discussiones Mathematicae Graph Theory
PY - 2008
VL - 28
IS - 3
SP - 383
EP - 392
AB - 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$.
LA - eng
KW - locating-total domination; differentiating-total domination; trees
UR - http://eudml.org/doc/270636
ER -