Authors:
M. Lu, W. Ning , K. Wang
Title:
Bounds on the locating-total domination number in trees
Source:
Discussiones Mathematicae Graph Theory
Received 22.05.2017, Revised 10.01.2018, Accepted 10.01.2018, doi: 10.7151/dmgt.2112

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\setminus 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). We show that, for a tree T of order n≥ 3 and diameter d, \frac{d+1}{2}≤ γtL(T)≤ n-\frac{d-1}{2}, and if T has l leaves, s support vertices and s1 strong support vertices, then γtL(T)≥\max{\frac{n+l-s+1}{2}-\frac{s+s1}{4},\frac{2(n+1)+3(l-s)-s1}{5}}. We also characterize the extremal trees achieving these bounds.
Keywords:
tree, total dominating set, locating-total dominating set, locating-total domination number

Links:
PDF