Metric-Locating-Dominating Sets in Graphs

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,\dots ,v_k\}$ be a set of vertices in a connected graph $G$. For each $v\in V(G)$, the $k$-vector $c_S(v)$ is defined by $c_S(v)=(d(v,v_1),d(v,v_2),\dots ,d(v,v_k))$. A dominating set $S=\{v_1,v_2,\dots ,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\in V(G)$ are distinct. The metric-location-domination number ${\gamma }_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 $\gamma (T)={\gamma }_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 ${\gamma }_L(T)/{\gamma }_M(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\ge 2$, then ${\gamma }_M(G)=n-1$ if and only if $G=K_{1,n-1}$ or $G=K_n$. The connected graphs $G$ of order $n\ge 4$ for which ${\gamma }_M(G)=n-2$ are characterized in terms of seven families of graphs.