Bounds on the Locating-Total Domination Number in Trees

Abstract

Given a graph G = (V, E) with no isolated vertex, a subset S of V is called a total dominating set of G if every vertex in V has a neighbor in S. A total dominating set S is called a locating-total dominating set if for each pair of distinct vertices u and v in V \ S, N(u) ∩ S ≠ N(v) ∩ S. The minimum cardinality of a locating-total dominating set of G is the locating-total domination number, denoted by γtL(G)\gamma _t^L ( G ) . We show that, for a tree T of order n ≥ 3 and diameter d+12≤γtL(T)≤n−d−12{{d + 1} \over 2} \le \gamma _t^L ( T ) \le n - {{d - 1} \over 2} , and if T has l leaves, s support vertices and s1 strong support vertices, then γtL(T)≥max{n+l−s+12−s+s14,2(n+1)+3(l−s)−s15}\gamma _t^L ( T ) \ge \max \left\{ {{{n + l - s + 1} \over 2} - {{s + {s_1}} \over 4},{{2 ( {n + 1} ) + 3 ( {l - s} ) - {s_1}} \over 5}} \right\} . We also characterize the extremal trees achieving these bounds.

Keywords

• tree
• total dominating set
• locating-total dominating set
• locating-total domination number
• 05c69