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(1), v(2),..., v(k)} be a set of vertices in a connected graph G. For each v is an element of V(G), the k-vector cs(v) is defined by cs(v) = (d(v, v(1)), d(v, v(2)),..,d(v,v(k))). A dominating set S = {v(1), v(2),..., v(k)} in a connected graph G is a metric-locating-dominating set, or an MLD-set, if the k-vectors cs(v) for v is an element of V (G) are distinct. The metric-location-domination number gammam(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 gamma(T) = gammam(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 gamma(L)(T)/gammam (T) is bounded above by 2, where -gamma(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 greater than or equal to 2, then gammam(T) = n-1 if and only if G = K-1,(n-1) or G = K-n. The connected graphs G of order n greater than or equal to 4 for which gammam(T) = n - 2 are characterized in terms of seven families of graphs.