Trees with Certain Locating-Chromatic Number

The locating-chromatic number of a graph G can be defined as the cardinality of a minimum resolving partition of the vertex set V(G) such that all vertices have distinct coordinates with respect to this partition and every two adjacent vertices in G. are not contained in the same partition class. In this case, the coordinate of a vertex v in G is expressed in terms of the distances of v to all partition classes. This concept is a special case of the graph partition dimension notion. Previous authors have characterized all graphs of order n with locating-chromatic number either n or n - 1. They also proved that there exists a tree of order n, n >= 5, having locating-chromatic number.. if and only if k is an element of{3,4, . . . , n - 2, n}. In this paper, we characterize all trees of order n with locating-chromatic number n - t, for any integers n and t, where n > t + 3 and 2 <= t < n/2.