On locating and differentiating-total domination in trees

Mustapha Chellali

Discussiones Mathematicae Graph Theory, Tome 28 (2008), p. 383-392 / Harvested from The Polish Digital Mathematics Library

Access to full text
Full (PDF)

Résumé

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) \geq m a x 2 (n + l - s + 1) / 5, (n + 2 - s) / 2$ , and for a tree of order n ≥ 3, $γ ₜ^{D} (T) \geq 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$ .

Publié le : 2008-01-01

Zbl 1173.05034

EUDML-ID : urn:eudml:doc:270636

@article{bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1414,
     author = {Mustapha Chellali},
     title = {On locating and differentiating-total domination in trees},
     journal = {Discussiones Mathematicae Graph Theory},
     volume = {28},
     year = {2008},
     pages = {383-392},
     zbl = {1173.05034},
     language = {en},
     url = {http://dml.mathdoc.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1414}
}

Mustapha Chellali. On locating and differentiating-total domination in trees. Discussiones Mathematicae Graph Theory, Tome 28 (2008) pp. 383-392. http://gdmltest.u-ga.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1414/

Bibliographie

[000] [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. | Zbl 1136.05049

[001] [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. | Zbl 1114.05071

[002] [3] J. Gimbel, B. van Gorden, M. Nicolescu, C. Umstead and N. Vaiana, Location with dominating sets, Congr. Numer. 151 (2001) 129-144. | Zbl 0996.05095

[003] [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. | Zbl 1091.05051