## Abstract

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 ∈ V(G), the k-vector cs(v) is defined by c_{S}(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 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.

Original language | English |
---|---|

Pages (from-to) | 129-141 |

Number of pages | 13 |

Journal | Ars Combinatoria |

Volume | 73 |

Publication status | Published - Oct 2004 |

Externally published | Yes |

## Keywords

- Dominating set
- Locating set
- Metric-locating-dominating set

## ASJC Scopus subject areas

- General Mathematics