# On locating and differentiating-total domination in trees

Discussiones Mathematicae Graph Theory (2008)

- Volume: 28, Issue: 3, page 383-392
- ISSN: 2083-5892

## Access Full Article

top## Abstract

top## How to cite

topMustapha 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 -

## References

top- [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. Zbl1136.05049
- [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. Zbl1114.05071
- [3] J. Gimbel, B. van Gorden, M. Nicolescu, C. Umstead and N. Vaiana, Location with dominating sets, Congr. Numer. 151 (2001) 129-144. Zbl0996.05095
- [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. Zbl1091.05051

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.