Distance neighbourhood pattern matrices

Abstract

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 $N_j^M[u] = {v ∈ M : d(u, v) = j}$. Clearly, then $N_j[u] = N_j^{V(G)}[u]$. B.D. Acharya [2] defined the M-eccentricity of u as the largest integer for which $N_j^M[u]neq phi$ and the p ×(dG +1) nonnegative integer matrix $D^M_G=(|N_j^M[v_i]|) called the M-distance neighborhood pattern (or, M-dnp) matrix of G. The matrix $D^{∗M}_G$ is obtained from $D^M_G$ by replacing each nonzero entry by 1. Clearly, $f_M(u) = {j:N_j^M[u]neq phi}$. Hence, in particular, if $f_M : u → f_M(u)$ is an injective function, then the set M is a distance-pattern distinguishing set (or, a ‘DPD-set’ in short) of G and G is a dpd-graph. If $f_M(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 [5] and design of indices of “quantitative structure activity relationships” (QSAR) in chemistry [3, 10]. This paper is a study of M-dnp matrices of a dpd-graph. 2000 Mathematics Subject Classifications: 05C78