On Average Distance of Neighborhood Graphs and Its Applications

Abstract

Graph invariants such as distance have a wide application in life, in particular when networks represent scenarios in form of either a bipartite or non-bipartite graph. Average distance μ of a graph G is one of the well-studied graph invariants. The graph invariants are often used in studying efficiency and stability of networks. However, the concept of average distance in a neighborhood graph G′ and its application has been less studied. In this chapter, we have studied properties of neighborhood graph and its invariants and deduced propositions and proofs to compare radius and average distance measures between G and G′. Our results show that if G is a connected bipartite graph and G′ its neighborhood, then radG1′≤radG and radG2′≤radG whenever G1′ and G2′ are components of G′. In addition, we showed that radG′≤radG for all r≥1 whenever G is a connected non-bipartite graph and G′ its neighborhood. Further, we also proved that if G is a connected graph and G′ its neighborhood, then and μG1′≤μG and μG2′≤μG whenever G1′ and G2′ are components of G′. In order to make our claims substantial and determine graphs for which the bounds are best possible, we performed some experiments in MATLAB software. Simulation results agree very well with the propositions and proofs. Finally, we have described how our results may be applied in socio-epidemiology and ecology and then concluded with other proposed further research questions.

1. Introduction

Graph theory is an important branch of discrete mathematics. The field has several important applications in areas of operations research, and applied mathematics. In graph theory, distance measures play an important role, in particular diameter and radius are two fundamental graph invariants. Their most important applications are in the analysis of networks, in particular social and economic networks [1], Information and Technological networks [2, 3, 4], Biological networks [5], Transportation networks [6, 7, 8], and facility location problems [9, 10]. The other important graph invariant is average distance. The average distance has applications in operations research, chemistry, social sciences, and biology [11, 12, 13, 14, 15, 16].

The average distance has been well-studied in literature [17, 18, 19, 20, 21, 22, 23, 24, 25] because of its own graph-theoretical interest and its numerous applications in communication networks, physical chemistry and geometry. For instance, in a transport network model, the time delay from one point to another is often proportional to the number of edges a commuter/transporter must travel [26]. The average distance can therefore be used to measure the efficiency of information or mass transport on a network [27, 28, 29]. In real network like World Wide Web, a short average path length facilitates the quick transfer of information and reduces costs. However, in a metabolic network, the efficiency of mass transfer can be judged by studying its average path length [11]. On the other hand, a power grid network can have less loss of energy transfer if its average path length is minimized [2, 4].

Furthermore, neighborhood graphs have received considerable attention in the literature [30, 31, 32, 33, 34, 35, 36, 37, 38, 39]. Their applications have hugely been reported in the field of biology especially in ecosystems where the predator–prey relationships have been modeled by undirected graphs called competition graphs [40]. In particular, [34] deduced that every neighborhood graph is a competition graph. The vertices in this graph represent species in the ecosystem and we connect two species by an edge if and only if the two species have common predator [5]. Thus, the neighborhood graph $G^{\prime }$ of a graph $G$ has the same vertex set as $G$, that is, $V\left(G\right)=V\left(G^{\prime }\right)$, and two vertices $u$, $v$ are adjacent in $G^{\prime }$ if and only if they have a common neighbor in $G$ (if and only there exists a path of length 2 between $u$ and $v$ in $G$). Thus, the neighborhood of a vertex $v$ in a graph $G$ is the subgraph of $G$ denoted by $G^{\prime }$ and induced by all vertices adjacent to $v$ [34]. Hence, the graph $G^{\prime }$ comprises the vertices adjacent to $v$ and all edges connecting vertices adjacent to $v$. Other applications of neighborhood graphs have as well been reported, for instance, in spanning tree [38] and pattern recognition [39] problems.

We now mention a few results on average distance and neighborhood graphs. For example, [27] proved the conjecture $\mu \left(G\right)\le \alpha \left(G\right)$ posed in [41] describing the connection between average distance $\mu$ and independence number $\alpha$ for complete graphs, i.e. for $\alpha =1$. The results were extended by [28] to include an upper bound of $\mu$ dependent on $n$ (order of a graph) as well. In [29], the relationship between average distance and domination number was considered. A generalization of these results was presented by [42]. In the same year 2009, [43] explored the concept of neighborhood number and its relationship with other parameters including domination number. The common neighborhood number and an algorithm for constructing have been discussed at length and presented also in [30]. Just as with average connectivity, average degree and average distance invariants, the common neighborhood number is also used as a measure for reliability and stability of a graph [33, 43].

On the other hand, [44] considered graphs $G$ such that the neighborhood graph $G^{\prime }$ is isomorphic to the compliment of $G$. In 2012, [31] studied the energy of common neighborhood graphs and its properties without considering average distance or their applications to current trends of research. Perhaps their research was motivated by a study of [26] who considered devising an algorithm for computing the average distance, radius and centre of a Circular-Arc Graph in parallel. However, [26] did not consider neighbourhoodness of the corresponding circular-arch graphs.

In this chapter, we therefore study properties of a neighborhood graph and compare its radius and average distance to that of the original graph. In particular we show that if $G^{\prime }$ is the neighborhood graph of a graph $G$ and $G$ is bipartite, then $\mathit{rad}\left(G_1^{\prime }\right)\le \mathit{rad}\left(G\right)$ and $\mu \left(G_1^{\prime }\right)\le \mu \left(G\right)$ or $\mathit{rad}\left(G_2^{\prime }\right)\le \mathit{rad}\left(G\right)$ and $\mu \left(G_2^{\prime }\right)\le \mu \left(G\right)$ where $G_1^{\prime }$ and $G_2^{\prime }$ are components of $G^{\prime }$. Also, if $G$ is non-bipartite, $\mathit{rad}\left(G^{\prime }\right)\le \mathit{rad}\left(G\right)$ and $\mu \left(G^{\prime }\right)\le \mu \left(G\right)$. We chose to study the radius and average distance of both bipartite and non-bipartite graphs because of their useful applications in network model analysis [2, 40, 45]. This study addresses specifically the following three important questions: [1] Do the radius and average distance of a neighborhood graph differ from those of original graph? [2] If so, what are the underlying graph characteristics or properties contributing to the differences? [3] In what context can the results be applied in real life scenario?

The rest of the chapter is organized as follows. In Section 2, we describe the procedure that led to answering the study research questions. Basic graph definitions, terminologies and other illustrations useful for the study approach have been presented in Section 3. The main findings of the study are presented and discussed in sections 4 and 5, respectively. Then, we demonstrate the applications of our results to socio-epidemiology and ecology in Section 6. Finally, in Section 7, we devote our attention to the conclusions and then draw out some recommendations for further research.

2. Our approach

In order to address the said research questions, we first assumed dealing with undirected simple bipartite and non-bipartite graphs. We then provided basic definitions and various graph terminologies as a preface to our main study findings. When stated without any qualification or reference to a particular vertex, a neighborhood graph is assumed to be open, otherwise closed [36]. In this chapter, we assumed dealing with an open neighborhood graph and simply used the term “neighborhood graph”. Furthermore, in some cases, we assumed $\mathit{G}$ to be locally ${\mathit{G}}^{\prime }$ [46], i.e. all vertices in $\mathit{G}$ have neighborhoods that are isomorphic to the same graph ${\mathit{G}}^{\prime }$, given $\mathit{f}:\mathit{V}\left(\mathit{G}\right)\to \mathit{V}\left({\mathit{G}}^{\prime }\right)$. Several questions regarding isomorphisms involving ${\mathit{G}}^{\prime }$ which were raised by [35] including that of ${\mathit{G}}^{\prime }\simeq \mathit{G}$ whenever $\mathit{G}$ is either complete graph ${\mathit{K}}_{\mathit{p}},\mathit{p}\ge \mathbf{2}$ or an odd cycle ${\mathit{C}}_{\mathbf{2}\mathit{k}+\mathbf{1}},\mathit{k}\ge \mathbf{1}$ have been addressed in [44]. We made use of some of these important isomorphic properties [44] when devising our proofs. We have described the main results in form of propositions and proofs in comparison with related findings of 31] and others in literature [28, 41, 47, 48] . In order to validate our findings, we ran some experiments on simulated graph data sets in MATLAB R2015a software. This approach has also been considered by other researchers [12, 13, 15, 16]. We then identified two important areas of application in which our major findings are applicable. Recognizing that our research contribution falls into a Graph Theory book, we have provided alternative proofs in Appendix 8.1 in order to justify the findings and provide the reader with an a different flavor of the approach.

3. Basic definitions

A graph$G=\left(V,E\right)$ is a collection of ordered pairs of vertex set $V=\left\{v_1,v_2,\dots ,v_n\right\}$ and edge set $=\left\{\left\{v_i,v_j\right\}:v_i,v_j\in V\right\}$, where each edge is an unordered pair of vertices from the set $V$. In this chapter we consider undirected graphs.

Definition 1 [49]. A subgraph of a graph is some smaller portion of that graph. Further, an induced (generated) subgraph is a subset of the vertices of the graph together with all the edges of the graph between the vertices of this subset.

Definition 2 [47]. The neighborhood of a vertex $v$, denoted by $N\left(v\right)$, is the subgraph induced by $v$ and all of its neighbors; sometimes referred to as the closed neighborhood of $v$.

The neighborhood graph of $G$, in general, denoted by $G^{\prime }$, refers therefore to the graph with the same vertex set as $G$ in which two vertices are adjacent if and only if they have a common neighbor in $G$. Figure 1 presents an example of a neighborhood graph $G^{\prime }$ (right) within a larger network structure $G$ .

For example, given a graph $G$ in Figure 1 (top), we first construct the open neighborhood sets for each corresponding vertices as $N\left(1\right)=\left\{2,3,4\right\}$, $N\left(2\right)=\left\{1,3\right\}$,$N\left(3\right)=\left\{1,2\right\}$ and $N\left(4\right)=\left\{1\right\}$. Then by the definition of neighborhood graph $G^{\prime }$, we define edges in $G^{\prime }$ via intersection of sets; $N\left(1\right)\cap N\left(2\right)=\left\{3\right\}$, $N\left(1\right)\cap N\left(3\right)=\left\{2\right\}$, $N\left(2\right)\cap N\left(3\right)=\left\{1\right\}$, $N\left(1\right)\cap N\left(4\right)=\varnothing$, $N\left(2\right)\cap N\left(4\right)=\left\{1\right\},N\left(4\right)\cap N\left(3\right)=\left\{1\right\}$. We then have two examples of $G^{\prime }$ shown in Figure 2 (bottom).

Figure 1.

A tree.

Definition 3 [12]. Given a connected graph $G$ with vertex set $V\left(G\right)$ of order $n$, the distance between two vertices $u,v$ of $G$, $d_G\left(u,v\right)$ is defined as the length of the shortest $u-v$ path in $G$. Thus, diameter of $G$, $\mathit{\text{diam}}\left(G\right)$ is the greatest distance among all pairs of vertices.

Definition 4 [15]. The radius of $G$, $\mathit{rad}\left(G\right)$, is the minimum eccentricity of $G$ where the eccentricity, ${\mathit{ec}}_G\left(v\right)$, of a vertex $v\in V\left(G\right)$ is the maximum distance between $v$ and any other vertex in $G$. A vertex $z\in V\left(G\right)$ is called central if ${\mathit{ec}}_G\left(v\right)=\mathit{rad}\left(G\right)$.

Definition 5 [28]. The average distance$\mu \left(G\right)$ of a connected graph $G$ of order $n$ is the average of distances between all pairs of vertices of $G$, i.e., $\mu \left(G\right)=\frac{2{\sum }_{\left\{u,v\right\}}{d}_G\left(u,v\right)}{n\left(n-1\right)}$where $d_G\left(u,v\right)$ denotes the distances between the vertices $u$ and $v$ in $G$.

Definition 6 [50]. The total distance of $G$ is defined as $d\left(G\right)={\sum }_{\left\{u,v\right\}\subseteq V\left(G\right)}d\left(u,v\right)$ while the total distance of a vertex $v$ is defined as $d\left(G\right)={\sum }_{u\in V-\left\{v\right\}}d\left(u,v\right)$.

Definition 7 [49]. A graph $G$ is bipartite if its vertex set can be partitioned into sets $U$ and $V$ in such a way that every edge of $G$ has one end vertex in $U$ and the other in $V$. In this case, $U$ and $V$ are called partite sets.

4. Results

4.1 Analytical results

In this section we deduce some important propositions and proofs relating average distance of a neighborhood graph to other graph parameters for both bipartite and non-bipartite graphs. Moreover, [47] showed that for any graph $G$, $G^{\prime }$ is bipartite. We first show that if $G$ if bipartite, then the radius of each component of the neighborhood graph of $G$ cannot exceed the radius of $G$.

Proposition 1. Let $G$ be a connected bipartite graph and let $G^{\prime }$ be its neighborhood graph. Consider $G_1^{\prime }$ and $G_2^{\prime }$ be two components of $G^{\prime }$. Then $\mathit{rad}\left(G_1^{\prime }\right)\le \mathit{rad}\left(G\right)$ and $\mathit{rad}\left(G_2^{\prime }\right)\le \mathit{rad}\left(G\right)$.

Proof. Let $G$ be a connected bipartite graph of radius $r$ and let $G^{\prime }$ be its neighborhood graph. Let $V\left(G_1\right)$ and $V\left(G_2\right)$ be two partitions of $V\left(G\right)$ and $G_1^{\prime }$ and $G_2^{\prime }$ be two components of $G^{\prime }$.

Case 1: Let $v_0,v_1\in V\left(G_1\right)$ such that $G_1^{\prime }$ is the component of $G^{\prime }$. Since $G$ is connected, then there exists a $v_0{v}_r$ path between any two vertices $v_0,v_r\in V\left(G\right)$. Let $v_0{v}_1{v}_2\cdots v_{r-1}{v}_r$ be a path connecting $v_0$ and $v_r$. But $G$ is bipartite and so $r-1$ must be odd. Then it follows that $r$ is even. Since $v_1$ is a common neighbor for $v_0$ and $v_2$, the two vertices $v_0$ and $v_2$ are adjacent in $G^{\prime }$. Similarly $v_2$ is adjacent to $v_4,\cdots ,v_{r-2}$ is adjacent to $v_r$ in $G^{\prime }$. Thus $d_{G^{\prime }}\left(v_0,v_r\right)=\frac{r}{2}$ since $r$ is even. Therefore $\mathit{rad}\left(G_1^{\prime }\right)\le \mathit{rad}\left(G\right)$.

Similarly, if $v_0,v_1\in V\left(G_2\right)$ and $G_2^{\prime }$ is the component of $G^{\prime }$, then $\mathit{rad}\left(G_2^{\prime }\right)\le \mathit{rad}\left(G\right)$

Case 2: Let $v_0\in V\left(G_1\right)$ and $v_r\in V\left(G_2\right)$ and let $G_1^{\prime }$ and $G_2^{\prime }$ be two components of $G^{\prime }$ By definition of neighborhood graph, these two vertices cannot be adjacent in $G^{\prime }$. If they were, there would exist a vertex $u$ adjacent to both $v_0$ and $v_r$ in $G$ which could not be found in either $V\left(G_1\right)$ and $V\left(G_2\right)$ which is impossible. Thus the vertices from $V\left(G_1\right)$ belong to one component, say $G_1^{\prime }$ and those from $V\left(G_2\right)$ to another component of $G^{\prime }$, say $G_2^{\prime }$ and so $\mathit{rad}\left(G_1^{\prime }\right)\le \mathit{rad}\left(G\right)$ or $\mathit{rad}\left(G_2^{\prime }\right)\le \mathit{rad}\left(G\right)$ if $v_0,v_1\in V\left(G_1\right)$ or $v_0,v_r\in V\left(G_2\right)$. This concludes the proof.

An alternative proof of proposition 1 is discussed in appendix 8.1. We next show that if $G$ is non-bipartite, then the radius of the neighborhood graph of $G$ cannot exceed the radius of $G$.

Proposition 2. Let $G$ be a connected non-bipartite graph and let $G^{\prime }$ be its neighborhood graph. Then $\mathit{rad}\left(G^{\prime }\right)\le \mathit{rad}\left(G\right),r\ge 1$.

Proof. Let $G$ be a connected non-bipartite graph and let $G^{\prime }$ be its neighborhood graph. Then $G$ contains an odd cycle. This cycle is also contained in $G^{\prime }$ (see Alwardi et al., 2012). Let $u_1$ and $u_2$ be two adjacent vertices on the odd cycle of $G$. Let $v_0\in V\left(G\right)$ such that $v_0$ is not equal to both $u_1$ and $u_2$. Let $v_0{v}_1{v}_2\cdots v_{r-1}{v}_r$ be a path connecting $v_0$ and $v_r$. We consider two cases:

Case 1: Suppose $r-1$ is odd. Then $r$ is even. Let $v_r=u_1$ and $v_0\ne u_1\left(u_2\right)$. Using similar proof as in Theorem 1, Case 1, we get $\mathit{rad}\left(G^{\prime }\right)\le \mathit{rad}\left(G\right)$.

Case 2: Suppose $r-1$ is even. Then $r$ is odd. Then we have a path $v_0{v}_1{v}_2\cdots v_{r-1}{v}_r$ connecting $v_0$ and $v_r$. Now let $v_r=u_2$. Thus, $d_{G^{\prime }}\left(v_0,v_2\right)=\frac{r+1}{2}$. Therefore, $\mathit{rad}\left(G^{\prime }\right)\le \mathit{rad}\left(G\right)$. This completes the proof. An alternative proof of Proposition 2 is also presented in Appendix 8.1.

To show that the bound in proposition 2 is best possible, let $T$ be a tree (Figure 1) such that every leaf of $T$ is of radius $\left(r\ge 1\right)$ from the central vertex. Connect any two leaves to obtain $G$ from $T$. Let $x$ be the central vertex of $T$ and let $v$ and $v^{\prime }$ be two leaves which are adjacent in $G$. This pair of vertices is contained in a cycle of length at most $2r+1$ in $G$. Thus, $d_G\left(v,v^{\prime }\right)\le r$. Hence, the radius of $G$ is $r$. But $\mathit{rad}\left(G^{\prime }\right)=\frac{r}{2}$ if $r$ is even and $\mathit{rad}\left(G^{\prime }\right)=⌊\frac{r}{2}⌋$ if $r$ is odd. Therefore, $\mathit{rad}\left(G^{\prime }\right)\le \mathit{rad}\left(G\right)$ We note that $\mathit{rad}\left(G^{\prime }\right)=\mathit{rad}\left(G\right)$ if $G$ is the cycle $C_{2r+1}$ since $G$ is isomorphic to $G^{\prime }$ (see [31]).

Figure 2.

Graph $G$ (top) and its neighborhood graph $G^{\prime }$(bottom). Source (authors).

Proposition 3. Let $G$ be a connected bipartite graph and let $G^{\prime }$ be its neighborhood graph. Let $G_1^{\prime }$ and $G_2^{\prime }$ be two components of $G^{\prime }$. Then $\mu \left(G_1^{\prime }\right)\le \mu \left(G\right)$ and $\mu \left(G_2^{\prime }\right)\le \mu \left(G\right)$. (Alternative to Proposition 5 and Corollary 1 discussed in Appendix 8.1).

Proof: we consider two cases.

Case 1: Let $v_0,v_r\in V\left(G_1\right)$ and let $G_1^{\prime }$ be the component of $G^{\prime }$. Since $G$ is connected, then there is a path connecting $v_0$ and $v_r$. Let $v_0{v}_1{v}_2\cdots v_{r-1}{v}_r$ be a path connecting $v_0$ and $v_r$. But $G$ is bipartite and so $r-1$ must be odd. It follows that $r$ is even.

Fix a vertex $v$ in $G$. For $i=0,1,2,\cdots ,r$, let $n_i$ be the number of vertices at distance $i$ from $v$. We first show that

$$d_G\left(v\right)=\frac{36n-2+\sqrt{1+6n\left(12n-2\right)}}{54}$$E1

Now

$$d_G\left(v\right)=1·n_1+2·n_2+\cdots +\left(r-1\right)·n_{r-1}+r{n}_r$$

$$=1+2+3+\cdots +r\left[n-\frac{r\left(r-1\right)}{2}\right]$$

$$=\frac{r\left(r-1\right)}{2}+\mathrm{nr}-\frac{r^2\left(r-1\right)}{2}$$

$$=r\left(n+\frac{r-1}{2}-\frac{r\left(r-1\right)}{2}\right)$$

$$d_G\left(v\right)=r\left(\frac{2n+2r-r^2-1}{2}\right)$$E2

But, $n={\sum }_{i=0}^r{n}_i\ge \frac{r^2-r}{2}$. Hence

$$2n\ge r^2-r$$E3

Without loss of generality, inequality [3] reduces to

$$2n+\frac{1}{4}\ge r^2-r+\frac{1}{4}$$

$$\Rightarrow 2n+\frac{1}{4}\ge {\left(r-\frac{1}{2}\right)}^2$$

$$={\left(2n+\frac{1}{4}\right)}^{\raisebox{1ex}{$1$}\!\left/ \!\raisebox{-1ex}{$2$}\right.}\ge r-\frac{1}{2}.$$

Hence,

$$r\le \frac{1}{2}+{\left(2n+\frac{1}{4}\right)}^{\raisebox{1ex}{$1$}\!\left/ \!\raisebox{-1ex}{$2$}\right.}=\frac{1}{2}+\frac{\sqrt{8n+1}}{2}$$

We differentiate $d_G\left(v\right)$ in Eq. (2) w.r.t. $r$ to get $\frac{d_G\left(v\right)}{\mathit{dr}}=n-\frac{3}{2}{r}^2+2r-\frac{1}{2}$. Now, when $\frac{\mathit{dr}}{\mathit{dv}}=0$, we have

$$1-2n=-3r^2+4r$$

$$-\frac{1}{3}+\frac{2}{3}n=r^2-\frac{4}{3}r={\left(r-\frac{2}{3}\right)}^2-\frac{4}{9}$$

$$\frac{1}{9}+\frac{2}{3}n={\left(r-\frac{2}{3}\right)}^2$$

$${\left(\frac{1}{9}+\frac{2}{3}n\right)}^{\raisebox{1ex}{$1$}\!\left/ \!\raisebox{-1ex}{$2$}\right.}=r-\frac{2}{3}$$

This implies that

$$r=\frac{2}{3}+\frac{\sqrt{1+6n}}{3}$$E4

Now $d_G\left(v\right)$ is maximized subject to the constraint $r\le \frac{1}{2}+\frac{\sqrt{8n+1}}{2}$ for $r=\frac{2}{3}+\frac{\sqrt{1+6n}}{3}$. Then we get

$$d_G\left(v\right)=\frac{36n-2+\sqrt{1+6n}\left(12n-2\right)}{54}$$

$$d_G\left(v\right)=\frac{18n-1+\sqrt{1+6n}\left(6n-1\right)}{27}.$$E5

But

$$\mu \left(G\right)=\frac{1}{n\left(n-1\right)}\sum _{v\in V}{d}_G\left(v\right)$$

$$=\frac{1}{n\left(n-1\right)}\sum _{v\in V}\frac{18n-1+\sqrt{1+6n}\left(6n-1\right)}{27}.$$

So that,

$$\mu \left(G\right)=\frac{18n-1+\sqrt{1+6n}\left(6n-1\right)}{27n\left(n-1\right)}.$$E6

Now fix a vertex $v$ in $G_1^{\prime }$. For, $i=0,1,2,\cdots \frac{r}{2}$, let $n_i$ be the number of vertices at distance $i$ from $v$. We next show that

$$d_{G_1^{\prime }}\left(v\right)=\frac{18n-2+\sqrt{\left(1+3n\right)}\left(6n+2\right)}{27}$$E7

Now,

$$d_{G_1^{\prime }}\left(v\right)=1+2+3+\cdots +\frac{r}{2}-1+\frac{r}{2}\left(n-\frac{r\left(r-1\right)}{4}\right)$$

$$=\frac{r\left(r-2\right)}{4}+\frac{\mathrm{nr}}{2}-\frac{r^2\left(r-2\right)}{8}$$

$$=\frac{2r\left(r-2\right)+4\mathrm{nr}-r^2\left(r-2\right)}{8}$$

$$=\frac{2r^2-4r+4\mathrm{nr}-r^3+2r^2}{8}$$

$$d_{G_1^{\prime }}\left(v\right)=\frac{4r^2-4r+4\mathit{nr}-r^3}{8}$$E8

But, $n={\sum }_{i=0}^r{n}_i\ge \frac{r\left(r-2\right)}{4}$. Hence,

$$4n\ge r^2-2r$$

$$4n+1\ge {\left(r-1\right)}^2$$

$$\sqrt{4n+1}\ge r-1$$

$$r\le 1+\sqrt{4n+1}$$

We differentiate $d_{G_1^{\prime }}\left(v\right)$ in Eq. (8) to get

$$\frac{\mathit{dv}}{\mathit{dr}}=\frac{1}{8}\left(8r-4+4n-3r^2\right)$$E9

Now, when $\frac{\mathrm{dv}}{\mathrm{dr}}=0$, solving for $r$ in Eq. (9), we get

$$r=\frac{4+\sqrt{12n+4}}{3}.$$E10

Therefore, substituting Eq. (10) into Eq. (8), we have

$$d_{G_1^{\prime }}\left(v\right)=\frac{r\left(r-2\right)}{4}+\frac{\mathrm{nr}}{2}-\frac{r^2\left(r-2\right)}{8}$$

$$=\frac{4r^2-4r+4\mathrm{nr}-r^3}{8}$$

$$=\frac{r^2\left(4-r\right)-4r\left(1-n\right)}{8}$$

$$d_{G_1^{\prime }}\left(v\right)=\frac{r}{8}\left(4n-{\left(r-2\right)}^2\right)$$E11

Now, if $d_{G_1^{\prime }}\left(v\right)$ in Eq. (11) is maximized subject to the constraint $r\le 1+\sqrt{4n+1}$ for $r=\frac{4+\sqrt{12n+4}}{3}$, we get

$$d_{G_1^{\prime }}\left(v\right)=\frac{r}{8}\left(4n-{\left(r-2\right)}^2\right)$$

$$=\left(\frac{4+2\sqrt{3n+1}}{24}\right)\left(\frac{\left(24n-8\right)+8\sqrt{3n+1}}{9}\right)$$

$$=\frac{18n-2+\left(6n+2\right)\sqrt{\left(3n+1\right)}}{27}$$

Now, from the fact that $\mu \left(G_1^{\prime }\right)=\frac{1}{n\left(n-1\right)}{\sum }_{v\in V}{d}_{G_1^{\prime }}\left(v\right)$, we have

$$\mu \left(G_1^{\prime }\right)=\frac{18n-2+\left(6n+2\right)\sqrt{\left(3n+1\right)}}{27n\left(n-1\right)}$$E12

Since $18n-1+\left(6n-1\right)\sqrt{\left(6n+1\right)}\ge 18n-2+\left(6n+2\right)\sqrt{\left(3n+1\right)}$, then we have $\mu \left(G_1^{\prime }\right)\le \mu \left(G\right)$. Similarly, $\mu \left(G_2^{\prime }\right)\le \mu \left(G\right)$. We conclude that $\mu \left(G_1^{\prime }\right)\le \mu \left(G\right)$ and $\mu \left(G_2^{\prime }\right)\le \mu \left(G\right)$ as agreeing with simulation results in Figure 3. This concludes the proof.

Figure 3.

Average distance against number of vertices in a graph.

Proposition 4. Let $G$ be a connected non-bipartite graph and let $G^{\prime }$ be its neighborhood graph. Then, $\mu \left(G^{\prime }\right)\le \mu \left(G\right)$ .

Proof. Let $G$ be a connected non-bipartite graph. Then $G$ contains an odd cycle. This cycle is also contained in $G^{\prime }$ (see [31]). Let $u_1$ and $u_2$ be two adjacent vertices on the odd cycle of $G$. Let $v_0\in V\left(G\right)$ such that $v_0$ is not equal to both $u_1$ and $u_2$. Let $v_0{v}_1{v}_2\cdots v_{r-1}{v}_r$ be a path connecting $v_0$ and $v_r$. We consider two cases:

Case 1: Suppose $r-1$ is odd. Then $r$ is even. Let $v_r=u_1$. Using similar proof as in Proposition 3, we get $\mu \left(G^{\prime }\right)\le \mu \left(G\right)$.

Case 2: Suppose $r-1$ is even. Then $r$ is odd. Then we have a path $v_0{v}_1{v}_2\cdots v_{r-1}{v}_r$ connecting $v_0$ and $v_r$. Now let $v_r=u_2$. Now that $\mu \left(G\right)$ will be the same as in Proposition 3. We just need to determine $\mu \left(G^{\prime }\right)$.

Fix a vertex $v$ in $G^{\prime }$. For, $i=0,1,2,\cdots \frac{r}{2}$, let $n_i$ be the number of vertices at distance $i$ from $v$. We show that

$$d_{G^{\prime }}\left(v\right)=\frac{\left(\lambda +1\right)\left(8n-{\lambda }^2+2\lambda -1\right)}{16}.$$E13

Now, by its definition,

$$d_{G^{\prime }}\left(v\right)=1+2+3+\cdots +\frac{r+1}{2}-1+\frac{r+1}{2}\left(n-\frac{r^2-1}{8}\right)$$

$$=\frac{r^2-1}{8}+\frac{r+1}{2}\left(n-\frac{r^2-1}{8}\right)$$

$$=\frac{r^2-1}{8}+\frac{n\left(r+1\right)}{2}-\left(\frac{\left(r+1\right)\left(r^2-1\right)}{16}\right)$$

$$=\frac{r^2-1}{8}\left(1-\left(\frac{r+1}{2}\right)\right)+\frac{n\left(r+1\right)}{2}$$

$$=\left(\frac{2r^2-2-r^3-r^2+r+1}{16}\right)+\frac{\mathrm{nr}+n}{2}$$

$$=\frac{-r^2\left(r-1\right)+\left(r-1\right)}{16}+\frac{\mathrm{nr}+n}{2}$$

$$=\frac{\left(1-r^2\right)\left(r-1\right)+8n\left(r+1\right)}{16}$$

$$d_{G^{\prime }}\left(v\right)=\frac{\left(r+1\right)\left(8n-{\left(r-1\right)}^2\right)}{16}$$E14

But,

$$n=\sum _{v\in V}i{n}_i\ge \frac{r^2-1}{8}$$

$$\Rightarrow 8n\ge r^2-1$$

$$\Rightarrow r\le \sqrt{8n+1}$$

We then differentiate $d_{G^{\prime }}\left(v\right)$ from Eq. (14) to get

$$\frac{\mathit{dv}}{\mathit{dr}}=\frac{1}{16}\left(8n-{\left(r-1\right)}^2-2\left(r^2-1\right)\right).$$E15

Now, when $\frac{\mathit{dv}}{\mathit{dr}}=0$ in Eq. (15), then $\frac{1}{16}\left(8n-{\left(r-1\right)}^2-2\left(r^2-1\right)\right)=0$ such that

$$r=\frac{1}{3}\left(2\sqrt{1+6n}\right)+1.$$E16

Further, if $d_{G^{\prime }}\left(v\right)$ of Eq. (14) is maximized, subject to the constraint $r\le \sqrt{8n+1}$ for $r=\frac{1}{3}\left(2\sqrt{1+6n}\right)+1$, it can easily be shown that

$$d_{G^{\prime }}\left(v\right)=\frac{\left(r+1\right)\left(8n-{\left(r-1\right)}^2\right)}{16}.$$E17

This implies that by substituting Eq. (16) into Eq. (17), we get

$$d_{G^{\prime }}\left(v\right)=\frac{{\left(\frac{1}{3}\left(2\sqrt{\left(1+6n\right)}+1\right)\right)}^2+\frac{2}{3}\left(2\sqrt{\left(1+6n\right)}+1\right)}{16}$$E18

Let $\frac{1}{3}\left(2\sqrt{\left(1+6n\right)}+1\right)=\lambda$ in Eq. (18). Then we have

$$d_{G^{\prime }}\left(v\right)=\frac{\left(\lambda +1\right)\left(8n-{\lambda }^2+2\lambda -1\right)}{16}.$$E19

Now, from the fact that $\mu \left(G^{\prime }\right)=\frac{1}{n\left(n-1\right)}{\sum }_{v\in V}{d}_{G_1^{\prime }}\left(v\right)$, we have

$$\mu \left(G^{\prime }\right)=\frac{1}{n\left(n-1\right)}\sum _{v\in V}{d}_{G_1^{\prime }}\left(v\right)=\frac{\left(\lambda +1\right)\left(8n-{\lambda }^2+2\lambda -1\right)}{16n\left(n-1\right)}.$$E20

Since $\frac{18n-1+\sqrt{1+6n}\left(6n-1\right)}{27n\left(n-1\right)}\ge \frac{\left(\lambda +1\right)\left(8n-{\lambda }^2+2\lambda -1\right)}{16n\left(n-1\right)}$, we have $\mu \left(G^{\prime }\right)\le \mu \left(G\right)$ as evidenced by Figure 4. This concludes the proof.

Figure 4.

Comparison of average distances for both bipartite and non-bipartite graphs.

As a consequence of our results, we state the following conjecture with respect to a bound of average distance of a graph in terms of independence number given in 27]. We do not prove it here. However, the conjecture compares very well with that of 41] and can therefore be extended also to include $n$ on its upper bound as procedure described in [28].

Conjecture 1. Given a graph $G$ such that $\mu \left(G\right)\le \alpha \left(G\right)$ where $\alpha \left(G\right)$ denotes the independent number of the graph $G$ [27], then for the corresponding neighborhood graph $G^{\prime }$, it also follows that $\mu \left(G^{\prime }\right)\le \alpha \left(G\right)$ and $\alpha \left(G^{\prime }\right)\le \alpha \left(G\right)$.

4.2 Simulation results

In this section, we present a simulation of our key results, i.e. $\mu \left(G_1^{\prime }\right)\le \mu \left(G\right)$ and $\mu \left(G^{\prime }\right)\le \mu \left(G\right)$ . We used MATLAB package to check our bounds established in propositions 1, 3, and 4. The results given in Figure 3 are in agreement with the established proofs.

More clearly, Figure 4 in Appendix 6.3 indicates that, for a large set of vertices, our results are indeed true for both bipartite and non-bipartite graphs. We thus show their application to real life, beginning with socio-epidemiology and then ecology in Section 7.

5. Discussion

Both the analytical and simulation results from this chapter highlight several important aspects worth further attention. The average distance of a neighborhood graph is indeed related to other graph parameters for both bipartite and non-bipartite graphs. These findings support other research with graph invariants and order of the graph [24, 26, 27, 28, 29, 42, 48, 51, 52, 53] indicating that our methodology of establishing the propositions and proofs relates very well with literature. While the methodology we took to arrive at the results is in line with those of [28, 31, 47], we went further by including in the notions of validation through simulations and also providing alternative proofs for the readers. These two aspects were not considered in their papers. In addition, in spite of [47] showing that “every neighbourhood graph is bipartite”, we have still subjected our analysis for both bipartite and non-bipartite cases. In that way, our established results are not limited to only bipartite graphs and thereby also giving a wider scope of their applications in real-life setting.

Other than using data from real-world complex network during simulations as in [12, 13], we had limited ourselves to the computer generated random undirected graphs with an intention of validating the analytical findings only. Further, unlike in [16], we have not considered simulations for directed graphs. This is because at the onset, we assumed dealing with undirected simple graphs. Perhaps, in future, the process of arriving at our results, including that of simulation can also be replicated for directed graphs. However, these two limitations do not affect status of the established propositions and proofs because our simulations indicate that for an increased number of vertices (Figure 3), a more complex network in that case, the established relations are clearly seen. This is also true for both bipartite and non-bipartite networks (Figure 4). Perhaps, in future, we might consider validating the analytical findings further with complex networks drawn out of real-world data set.

The establishment of Conjecture 1 assumes that the concept of average distance in a neighborhood graph can be studied further in relation to other graph invariants or parameters. Nonetheless, the findings we have still demonstrate a wide range of their applications in real-life setting. However, in the next section, we limit our discussion in context of socio-epidemiology and ecology complex networks only.

6. Application

6.1 Socio-epidemiology

The concept of neighborhood can sometimes be used to define the clustering coefficient of a graph. A clustering coefficient measures the degree to which nodes in a graph tend to cluster together. For the vertex $v_i$ and it’s neighborhood $N_i$ defined by $N_i=\left\{v_j:e_{\mathit{ij}}\in E\cup e_{\mathit{ji}}\in E\right\}$, let $k_i$ be defined as the number of vertices,$\left|N_i\right|,$ in the neighborhood, $N_i$ of a vertex. The local clustering coefficient $C_i$ for a vertex $v_i$ is defined as a proportion of the number of links between the vertices within its neighborhood divided by the number of links that could possibly exist between them. Consequently, $C_i$ for the directed and undirected graphs would, respectively be described by

$$C_i=\frac{\left|\left\{e_{\mathit{jk}}:v_j,v_k\in N_i,e_{\mathit{jk}}\in E\right\}\right|}{k_i\left(k_i-1\right)}\text{and}{C}_i=\frac{2\left|\left\{e_{\mathit{jk}}:v_j,v_k\in N_i,e_{\mathit{jk}}\in E\right\}\right|}{k_i\left(k_i-1\right)}$$E21

Eq. (21) evidently suggests that in most real-world networks such as social networks, which can be modeled as undirected graphs, the degree of local cluster coefficient tends to be larger. This situation can be very problematic, in particular during fake rumor or disease spread, for example, the current pandemic of COVID-19. Studying the structure of such graph and its neighbourhoodness is therefore an ideal approach to controlling further rumor or disease spread. Epidemiologists will therefore be looking for methods or techniques of minimizing different variants of neighborhood graphs such as “average distance” properties deduced in propositions 1–5 of this chapter. Rather than focusing on the original network of community members, certain interventions may be worthy when addressed to the neighborhood network.

6.2 Ecology

In ecology, in particular when studying interactions between plant and animal species, often times, networks in form of bipartite graphs are used [11]. Such has been the case even to the extent of understanding the interactions between species through graph metrics such as species degree, connectance, strength and even nestedness of the mutualistic network presented as a bipartite graph [54, 55, 56]. Indirect usage of neighborhood graphs in ecology is seen when researchers tend to investigate how interacting species respond to either a disturbance or composition change in a given environment [57]. Of note is the concept of “interaction wiring” which occurs when same species are found in both networks but with different connections [58]. This concept is similar to that of having an original network $G$ and a disturbed network $G^{\prime }$, but both having same species [40]. Therefore, the relationship between average distance of two graphs $G$ and $G^{\prime }$ deduced in this chapter should therefore be more useful network metric in ecological studies as well, in particular for the case of studying interaction wiring. If such concept is applied, it should then be well understood that in a disturbed environment, plant–animal species interaction, for example, would therefore display a different behavior all together because of different closeness metric.

7. Conclusions

In this chapter we have re-introduced the notion of neighborhood graph and in particular discussed at length, the average distance metric. Neighborhood graphs and its graph invariants have been studied by many [31, 33, 34, 35, 37, 38, 39, 43]. However, the relationship between the average distance of neighborhood graph $G^{\prime }$ and graph $G$ was less explored. Therefore, some important results describing such relationship have been derived and presented by Theorems 1–5 and Corollary 1. To validate the results, data calibration has been done in MATLAB with results (Figure 3) excellently agreeing with the theory. Further, we have included two important areas of application of our results in epidemiology and ecology studies.

There are several directions for further research. First, we believe that the average distance concepts that we have discussed in this chapter can also be extended to other forms of graphs such as $\gamma$-neighborhood graphs [32]. Therefore, in future, it should be possible then to also extend these notions and explore the relationships of average distance, neighborhood number and denomination number of $\gamma$-neighborhood graphs.

Secondly, just as with $\gamma$-graphs, we need development of more computer algorithms for constructing neighborhood graphs and its associated invariants discussed here. This should be considered as most urgent to drive the application agenda which seems to be far much behind than the theory. Of course, [26] considered devising an algorithm for computing the average distance, radius and centre of a Circular-Arc Graph in parallel. However, the structure of the graphs were not of the neighborhood property. This would therefore be a starting point.

A final open and challenging research suggestion is the construction of neighborhood graphs on sets of edges (either weighted or non-weighted). This would be a most remarkable contribution towards usage of graphs in percolation theory. The proposal of constructing neighborhood graphs on weighted sites (nodes/vertices) was also mentioned in [32].

Acknowledgments

This work was undertaken with financial support from University of Malawi, Chancellor College through institutional research grant.

Conflict of interest

An abstract of this chapter appears at https://mwakilamae.wixsite.com/scientist-site/ based on the preliminary results of the paper which were also presented at the 2015 SAMSA conference in Namibia. However, no full paper was submitted or published with any conference proceedings. Therefore, the authors declare no conflict of interest.

A.1 Alternative proofs

Proof of proposition 1.

Let $e_i\in {\mathbb{R}}^n$ be a basis, and $D_G$ be the distance matrix for graph $G$. Then by the definition of eccentricity, ${\mathit{ec}}_G\left(i\right)=\mathit{max}\left(e_i^T{D}_G\right)$ of vertex $i$. Similarly, the definition of radius implies that $\mathit{rad}\left(G\right)=\mathit{min}\left(\left\{\mathit{max}\left(e_i^T{D}_G\right):i=1,2,3,\cdots ,n\right\}\right)$. Since $G$ is connected, then there are $\frac{n\left(n-1\right)}{2}$ graph geodesics in $G$. That is, that there are $n\left(n-1\right)$ non-zero entries in $D_G$. But $G$ is bipartite, then, it has two sets of vertices $V_1$ and $V_2$ which belong to the components $G_{N_t}$, for $t=1,2$. Further, by definition of neighborhood graph, it follows then that $\left|V_1\right|+\left|V_2\right|=n$, such that $\left|V_1\right|,\left|V_2\right|<n$. This means each graph geodesic in the components is of length less than that of $G$.

Without loss of generality, let $\frac{\left|V_t\right|\left(\left|V_t\right|-1\right)}{2}$ be the graph geodesic for each component $G_{N_t}$. This implies that the number of non-zero components in $G_{N_t}$ is $\left|V_t\right|\left(\left|V_t\right|-1\right)<n\left(n-1\right)$ . Therefore,

$$e_i^T{D}_{G_{N_t}}{e}_j\le e_i^T{D}_G{e}_j$$

$$\forall t=1,2;max\left(e_i^T{D}_{G_{N_t}}\right)\le max\left(e_i^T{D}_G\right)$$

$$\Rightarrow min\left(\left\{max\left(e_i^T{D}_{G_{N_t}}\right):i=1,2,3,\cdots ,\left|V_t\right|\right\}\right)\le min\left(\left\{max\left(e_i^T{D}_G\right):i=1,2,3,\cdots ,n\right\}\right)$$

Therefore, $\mathit{rad}\left(G_{N_t}\right)\le \mathit{rad}\left(G\right)$ .

Proof of proposition 2.

Let $G$ be a connected non-bipartite graph and let $G^{\prime }$ be its neighborhood graph with their respective distance matrices $D_G$ and $D_{G^{\prime }}$. By definition of neighborhood graph, then$G^{\prime }$ is also connected and non-bipartite [31]. Thus, both $G$ and $G^{\prime }$ contain an odd cycle [49, 59]. In particular, both $G$ and $G^{\prime }$ have the same odd cycle [31]. Let $u_1$ and $u_2$ be two adjacent vertices on the odd cycle of $G$. Let $C_{2k+1},k\in \mathbb{N}$ be such a cycle. We consider two cases:

Case 1: Suppose $G=C_{2k+1}$. Then accordingly, $G=C_{2k+1}=G^{\prime }$ such that $D_G=D_{G^{\prime }}$ . In particular, $G\simeq G^{\prime }$ (see [44], Theorems 4 and 5). Using similar proof as in Theorem 1, we have

$$min\left(\left\{max\left(e_i^T{D}_G\right):i=1,2,\cdots ,2k+1\right\}\right)\le min\left(\left\{max\left(e_i^T{D}_{G^{\prime }}\right):i=1,2,\cdots ,2k+1\right\}\right),$$

such that we get $\mathit{rad}\left(G^{\prime }\right)=\mathit{rad}\left(G\right)$.

Case 2: Suppose $G\ne C_{2k+1}$. Let $v_0{v}_1{v}_2\cdots v_{r-1}{v}_r{v}_{r+1}{v}_{r+2}$ be a path connecting $v_0$ and $v_{r+2}$ on the cycle $C_{2k+1}$ in $G$. Let us consider then any two arbitrary vertices $u_1$ and $u_r$ not in $C_{2k+1}$ but available in $G$. Further let $v_0\in V\left(C_{2k+1}\right)$ such that $u_r\cdots u_1{v}_0$ is a path in $G$ because $G$ is connected. Suppose $v_0=v_{j+1}$. Then by definition of neighborhood graph, $u_1$ is adjacent to $v_j$ and $v_{j+2}$ contained in $G^{\prime }$. This means that every path $u_r\cdots u_1{v}_0$ is reduced by at least one edge length in order to form the graph $G^{\prime }$. Thus, the length of graph geodesics in $G^{\prime }$ are always lower than those in $G$. Then,

$$e_i^T{D}_{G^{\prime }}{e}_j\le e_i^T{D}_G{e}_j$$

$$\forall i=1,2,\cdots ,n;max\left(e_i^T{D}_{G^{\prime }}\right)\le max\left(e_i^T{D}_G\right)$$

$$\Rightarrow min\left(\left\{max\left(e_i^T{D}_{G^{\prime }}\right):i=1,2,3,\cdots ,n\right\}\right)\le min\left(\left\{max\left(e_i^T{D}_G\right):i=1,2,3,\cdots ,n\right\}\right)$$

Therefore, $\mathit{rad}\left(G^{\prime }\right)\le \mathit{rad}\left(G\right)$. Now, the simplest non-bipartite graph is $G=C_{2k+1}$ where $\mathit{rad}\left(G\right)=k\ge 1$ because $,k\in \mathbb{N}$. This completes the proof.

Proposition 5. Let $G^{\prime }$ be a neighborhood of a connected bipartite graph $G$. Let $G_t^{\prime },t=1,2$ be two components of $G^{\prime }$. Then

$$\frac{\mu \left(G_t^{\prime }\right)}{n\left(n-1\right)}\le \frac{\mu \left(G\right)}{\left|V_t\right|\left(\left|V_t\right|-1\right)},t=1,2$$E22

Proof. Let $G^{\prime }$ be the neighborhood graph of a bipartite graph $G$ and both simple. Further, suppose $G_t^{\prime },t=1,2$ are the two components of $G^{\prime }$. Then $e_i^T{D}_{G_t^{\prime }}{e}_i=0,\forall i=1,2,\cdots ,\left|V_t\right|$ . Likewise, $e_i^T{D}_G{e}_i=0,\forall i=1,2,\cdots ,n$ for the graph $G$. Then,

$$2\left(\sum _{\left\{u,v\right\}\in E\left(G\right)}{d}_G\left(u,v\right)\right)=\sum _{i=1}^n\sum _{j=1}^n{e}_i^T{D}_G{e}_j\text{and}2\left(\sum _{\left\{u,v\right\}\in E\left(G^{\prime }\right)}{d}_{G_t^{\prime }}\left(u,v\right)\right)=\sum _{i=1}^n\sum _{j=1}^n{e}_i^T{D}_{G_t^{\prime }}{e}_j.$$

We have already shown, previously, that $e_i^T{D}_{G_t^{\prime }}{e}_j\le e_i^T{D}_G{e}_j$ . Then, we may proceed to say that

$$\sum _{i=1}^n\sum _{j=1}^n{e}_i^T{D}_{G_t^{\prime }}{e}_j\le \sum _{i=1}^n\sum _{j=1}^n{e}_i^T{D}_G{e}_j,$$

which also implies that

$$2\left(\sum _{\left\{u,v\right\}\in E\left(G^{\prime }\right)}{d}_{G_t^{\prime }}\left(u,v\right)\right)\le 2\left(\sum _{\left\{u,v\right\}\in E\left(G\right)}{d}_G\left(u,v\right)\right).$$E23

If we divide the inequality [23] by $n\left(n-1\right)>0$ both sides, we have,

$$2\frac{\left({\sum }_{\left\{u,v\right\}\in E\left(G^{\prime }\right)}{d}_{G_t^{\prime }}\left(u,v\right)\right)}{n\left(n-1\right)}\le 2\frac{\left({\sum }_{\left\{u,v\right\}\in E\left(G\right)}{d}_G\left(u,v\right)\right)}{n\left(n-1\right)}.$$E24

The RHS of inequality [24] is equal to $\mu \left(G\right)$. Also, by construction, we have

$$\frac{\left|V_t\right|\left(\left|V_t\right|-1\right)\mu \left(G_t^{\prime }\right)}{n\left(n-1\right)}\le \mu \left(G\right).$$E25

Inequality [25] means that

$$\frac{\mu \left(G_t^{\prime }\right)}{n\left(n-1\right)}\le \frac{\mu \left(G\right)}{\left|V_t\right|\left(\left|V_t\right|-1\right)}.$$E26

Corollary 1. Let $G^{\prime }$ be a neighborhood of a connected bipartite graph $G$ such that $G_t^{\prime },t=1,2$ are the two components of $G^{\prime }$. Then, if

$$\frac{\mu \left(G_t^{\prime }\right)}{n\left(n-1\right)}\le \frac{\mu \left(G\right)}{\left|V_t\right|\left(\left|V_t\right|-1\right)},t=1,2$$E27

then $\mathit{\delta \mu }\left(G_t^{\prime }\right)<\mu \left(G\right),t=1,2$ whenever $\left|V_t\right|\left(\left|V_t\right|-1\right)<n\left(n-1\right)$. Consequently, for an infinitely small $\delta >0$, for $n\to \infty ,\mu \left(G_t^{\prime }\right)<\mu \left(G\right),\forall t=1,2$. Moreover this result is also true given that $\left|V_t\right|$ is the neighborhood number of $G_t^{\prime }$ (see [33, 43]).

Proof of proposition 4.

Let $G^{\prime }$ be its neighborhood graph of a connected non-bipartite graph $G$ be and with their respective distance matrices $D_{G^{\prime }}$ and $D_G$.

By Corollary 1, we have already shown that for a bipartite neighborhood graph $G_t^{\prime },$having two components $G_1^{\prime }$ and $G_2^{\prime }$,

$$\frac{\mu \left(G_t^{\prime }\right)}{n\left(n-1\right)}\le \frac{\mu \left(G\right)}{\left|V_t\right|\left(\left|V_t\right|-1\right)},t=1,2.$$E28

In general, if $G^{\prime }$ is non-partitioned, for all $t=1,2$, $\left|V_t\right|\left(\left|V_t\right|-1\right)=n\left(n-1\right)$. Then, the inequality [28] reduces to $\mu \left(G^{\prime }\right)\le \mu \left(G\right)$.

Notes/thanks/other declarations

Note that both MATLAB codes and simulated data files used to support the findings of this study (see Figure 4) are available from the corresponding author upon request. Further, PA, EM, and PC conceived and designed the study framework. PA, EM, PC, KM and LE analyzed the problem. PC and EM conducted the simulations in MATLAB. EM and PA wrote the paper. All authors read, reviewed and approved the final manuscript.

Nomenclature and mathematical symbols

Symbol

Interpretation

$G$

Graph

$G^{\prime }$

Neighborhood graph

$\mu \left(.\right)$

Average distance of

$d\left(.\right)$

Total distance of or geodesic distance

$d\left(.,.\right)$

Distance between two vertices

$V\left(.\right)$

Vertex set of

$\mathit{rad}\left(.\right)$

Radius of graph or minimum eccentricity

$r$

Node or vertex index or minimum distance of a node from center node

$n$

Number of nodes/vertices in a given graph or order of a given graph

$⌊.⌋$

Largest integer less than or equal to

$\sum _k.$

Sum of numbers indexed by $k$

$\lambda$

Parameter for the characteristic equation

$v$

Vertex

$d_G\left(v\right)$

Shortest distance of vertex $v$ from central vertex in a graph

$G\left(,.,\right)$

Bipartite graphs

${\mathit{ec}}_G\left(v\right)$

Maximum distance of vertex $v$ from any other vertex

$\mathit{\text{diam}}\left(.\right)$

Diameter of graph or maximum eccentricity

$E\left(.\right)$

Set of edges

≃

Isomorphism

$\left|V_t\right|$

Cardinality or number of elements

$\le$

Less than or equal to

$<$

Strictly less than

$\infty$

Infinity or larger number

$e_i^T$

Transpose of $e_i$

$C_p$

Cycle of length $p$

$K_p$

Complete graph with $p$ number of vertices

$\alpha$

Independent number of a graph