Distance-patterns of vertices in a graph

Given a connected simple (p, q)-graph G = (V,E) and ∅ = M ⊆ V, we initiate a study of the set-valued function f: V → 2M − {∅}, called the M-distance-pattern of G, which associates with each vertex u ∈ V the set fM (u) = {d(u, v) : v ∈ M}, called the M-distance pattern of u. Emphasis of this paper will be on graphs that admit ‘marker sets ’ M which render fM injective, whence we say that M is a-distance pattern distinguishing (or, ‘DPD-’) set of G. A graph is distance-pattern distinguishing (or, ‘DPD-graph’) if it admits a DPD-set. Let G = (V,E) be a given connected simple (p, q)-graph, and an arbitrary nonempty subset M ⊆ V (G) of G and for each v ∈ V (G), define NMj [u] = {v ∈ M: d(u, v) = j}. Clearly, then Nj[u] = NV (G)j [u]. The M-eccentricity of u as the largest integer for which NMj [u] = ∅ and the p × (dG + 1) nonnegative integer matrix DMG = (|NMj [vi]|), called the M-distance neighborhood pattern (or, M-dnp) matrix of G. The matrix D∗MG is obtained from D M G by replacing each nonzero entry by 1. If fM: u → fM(u) is an injective function then the set M is a distance-pattern distinguishing set (or, a ‘DPD-set ’ in short) of G and if fM(u)−{0} is independent of the choice of u in G then M is an open distance-pattern uniform (or, ODPU) set of G. A study of these sets is expected to be useful in a number of areas of practical importance such as facility location and design of indices of ‘quantitative structure-activity relationships ’ (QSAR) in chemistry. In this paper, we shall be mainly concerned with initiating a study of DPD-sets in a connected graph