PDF
Discussiones Mathematicae Graph Theory 28(3) (2008)
383-392
DOI: https://doi.org/10.7151/dmgt.1414
ON LOCATING AND DIFFERENTIATING-TOTAL DOMINATION IN TREES
Mustapha Chellali
LAMDA-RO Laboratory
Department of Mathematics
University of Blida
B.P. 270, Blida, Algeria
e-mail: m_chellali@yahoo.com
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 γtL(G) and γtD(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, γtL (T)≥max{2(n+l−s+1)/5,(n+2−s)/2}, and for a tree of order n ≥ 3, γtD(T) ≥ 3(n+l−s+1)/7, improving the lower bounds of Haynes, Henning and Howard. Moreover we characterize the trees satisfying γtL(T) = 2(n+l− s+1)/5 or γtD(T) = 3(n+l−s+1)/7.Keywords: locating-total domination, differentiating-total domination, trees.
2000 Mathematics Subject Classification: 05C69.
References
| [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. |
Received 20 April 2006
Revised 14 March 2008
Accepted 9 May 2008
Close