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, \ldots, 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), \ldots, d(v, v_k))\). A dominating set \(S = \{v_1, v_2, \ldots, 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 \geq 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 \geq 4\) for which \(\gamma_M(G) = n-2\) are characterized in terms of seven families of graphs.