Metric-locating-dominating sets in graphs

If u and v are vertices of a graph, then d(u, v) denotes the distance from u to v. Let S = {v₁, v₂, ... ,v_k} be a set of vertices in a connected graph G. For each v ∈ V(G), the k-vector cs(v) is defined by c_S(v) = (d(v, v₁), d(v, v₂), ⋯, d(v, v_k)). A dominating set S = {v₁, v ₂, ... , v_k} in a connected graph G is a metric-locating-dominating set, or an MLD-set, if the k-vectors c_S(v) for v ∈ V(G) are distinct. The metric-location-domination number γM(G) of G is the minimum cardinality of an MLD-set in G. We determine the metric-location-domination number of a tree in terms of its domination number. In particular, we show that γ(T) = γM(T) if and only if T contains no vertex that is adjacent to two or more end-vertices. We show that for a tree T the ratio γL(T)/γM(T) is bounded above by 2, where γL(G) is the location- domination number defined by Slater (Dominating and reference sets in graphs, J. Math. Phys. Sci. 22 (1988), 445-455). We establish that if G is a connected graph of order n ≥ 2, then γM(T) = n - 1 if and only if G = K_1,n-1 or G = K_n. The connected graphs G of order n ≥ 4 for which γM (T) = n - 2 are characterized in terms of seven families of graphs.