Distance-location numbers of graphs
Abstract
For a set S of vertices in a connected graph G, the distance of a vertex v with respect to S is defined by dS(v) = Σx∈Sd(v, x). If dS(u) ≠ dS(v) for each pair u, v of distinct vertices of G, then S is called a distance-locating set of G. The minimum cardinality of a distance-locating set of G is called its distance-location number locd(G). If dS(u) ≠ dS(v) for each pair u, v of distinct vertices of G - S, then S is called an external distance-locating set of G. The minimum cardinality of an external distance-locating set of G is called its external distance-location number loce(G). We study the existence of distance-locating sets in some well-known classes of connected graphs. It is shown that no distance-locating set in a connected graph G has cardinality 2 or 3. Moreover, there are infinite classes of connected graphs G for which locd(G) exists as well as infinite classes of connected graphs G for which locd(G) does not exist. Lower bounds for the distance-location and external distance-location numbers of a connected graph are established in terms of its order, diameter, and other parameters.
