Distance Neighbourhood Pattern Matrices in a Graph

Germina Kizhekekunnel Augustine, Alphy Joseph, Sona Jose

Abstract

Let $G = (V, E)$ be a given connected simple $(p, q)$-graph, and an arbitrary nonempty subset $M \subseteq V(G)$ of $G$ and for each $v \in V(G)$, define $N^M_j[u] = \{v \in M: d(u,v) = j\}$. Clearly, then $N_j[u] = N^{V(G)}_j[u]$. B. D. Acharya ~\cite{bda2} defined the $M${\it -eccentricity} of $u$ as the largest integer for which $N^M_j[u] \ne \emptyset$ and the $p\times (d_G+1)$ nonnegative integer matrix $D^M_G = (|N^M_j[v_i]|)$,  called the $M$-{\it distance neighborhood pattern} (or, $M${\it -dnp}) {\it matrix} of $G$. The matrix $D_G^{*M}$ is obtained from $D_G^M$ by replacing each nonzero entry by $1$. Clearly, $f_M(u) = \{j: N^M_j[u] \ne \emptyset\}$. Hence, in particular, if $f_M: u \mapsto f_M(u)$ is an injective function, then the set $M$ is a \emph{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 {\it open distance-pattern uniform} (or, ODPU) {\it 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  ~\cite{hm} and design of indices of `quantitative structure-activity relationships' (QSAR) in chemistry ~\cite{bmg,dhr}.  This paper is a study of  $M$-dnp matrices of a dpd-graph.

Keywords

Distance-pattern distinguishing sets, Distance neighborhood pattern matrix

Full Text:

PDF