## 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.

### Keywords

- Radius
- Average distance
- Neighborhood graph
- Bipartite graph
- Non-Bipartite graph

## 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

We now mention a few results on average distance and neighborhood graphs. For example, [27] proved the conjecture

On the other hand, [44] considered 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 * bipartite*, then

*,*non-bipartite

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

## 3. Basic definitions

A * vertex*set

*set*edge

** Definition 1**[49]. A

*of a graph is some smaller portion of that graph. Further, an*subgraph

*is a subset of the vertices of the graph together with all the edges of the graph between the vertices of this subset.*induced (generated) subgraph

** Definition 2**[47]. The neighborhood of a vertex

*of*closed neighborhood

The neighborhood graph of

For example, given a graph

** Definition 3**[12]. Given a connected graph

** Definition 4**[15]. The

*of*radius

*if*central

** Definition 5**[28]. The

average distance

** Definition 6**[50]. The total distance of

** Definition 7**[49]. A graph

*if its vertex set can be partitioned into sets*bipartite

*sets.*partite

## 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

** Proposition 1**. Let

. Let

** Case 1**: Let

Similarly, if

** Case 2**: Let

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

** Proposition 2**. Let

. Let

** Case 1**: Suppose

** Case 2**: Suppose

To show that the bound in proposition 2 is best possible, let

** Proposition 3**. Let

** Proof**: we consider two cases.

** Case 1**: Let

Fix a vertex

Now

But,

Without loss of generality, inequality [3] reduces to

Hence,

We differentiate

This implies that

Now

But

So that,

Now fix a vertex

Now,

But,

We differentiate

Now, when

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

Now, if

Now, from the fact that

Since

** Proposition 4**. Let

. Let

** Case 1**: Suppose

** Case 2**: Suppose

Fix a vertex

Now, by its definition,

But,

We then differentiate

Now, when

Further, if

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

Let

Now, from the fact that

Since

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

** Conjecture 1**. Given a graph

### 4.2 Simulation results

In this section, we present a simulation of our key results, i.e.

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

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

## 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

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

Secondly, just as with

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

Let

Without loss of generality, let

Therefore,

Let

** Case 1**: Suppose

such that we get

** Case 2**: Suppose

Therefore,

** Proposition 5**. Let

. Let

We have already shown, previously, that

which also implies that

If we divide the inequality [23] by

The RHS of inequality [24] is equal to

Inequality [25] means that

** Corollary 1**. Let

then

Let

By Corollary 1, we have already shown that for a bipartite neighborhood graph

In general, if

## 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

Interpretation

Graph

Neighborhood graph

Average distance of

Total distance of or geodesic distance

Distance between two vertices

Vertex set of

Radius of graph or minimum eccentricity

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

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

Largest integer less than or equal to

Sum of numbers indexed by

Parameter for the characteristic equation

Vertex

Shortest distance of vertex

Bipartite graphs

Maximum distance of vertex

Diameter of graph or maximum eccentricity

Set of edges

Isomorphism

Cardinality or number of elements

Less than or equal to

Strictly less than

Infinity or larger number

Transpose of

Cycle of length

Complete graph with

Independent number of a graph