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