Authors: N. Jafari Rad, H. Rahbani Title: Bounds on the locating-domination number and differentiating-total domination number in trees Source: Discussiones Mathematicae Graph Theory Received 07.09.2016, Revised 15.12.2016, Accepted 15.12.2016, doi: 10.7151/dmgt.2012 | |
Abstract: A subset S of vertices in a graph G=(V,E) is a dominating set of G if every vertex in V-S has a neighbor in S, and is a total dominating set if every vertex in V has a neighbor in S. A dominating set S is a locating-dominating set of G if every two vertices x,y∈V-S satisfy N(x)∩ S≠ N(y)∩ S. The locating-domination number γ_{L}(G) is the minimum cardinality of a locating-dominating set of G. A total dominating set S is called a differentiating-total dominating set if for every pair of distinct vertices u and v of G, N[u]∩ S≠ N[v]∩ S. The minimum cardinality of a differentiating-total dominating set of G is the differentiating-total domination number of G, denoted by γ_{t}^{D}(G). We obtain new upper bounds for the locating-domination number, and the differentiating-total domination number in trees. Moreover, we characterize all trees achieving equality for the new bounds. | |
Keywords: locating-dominating set, differentiating-total dominating set, tree | |
Links: |