Open access peer-reviewed chapter

On Average Distance of Neighborhood Graphs and Its Applications

Written By

Elias Mwakilama, Patrick Ali, Patrick Chidzalo, Kambombo Mtonga and Levis Eneya

Submitted: 21 May 2021 Reviewed: 19 June 2021 Published: 27 September 2021

DOI: 10.5772/intechopen.98986

From the Edited Volume

Recent Applications in Graph Theory

Edited by Harun Pirim

Chapter metrics overview

387 Chapter Downloads

View Full Metrics

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 G of a graph G has the same vertex set as G, that is, VG=VG, and two vertices u, v are adjacent in G 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 and induced by all vertices adjacent to v [34]. Hence, the graph G 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 μGαG posed in [41] describing the connection between average distance μ and independence number α for complete graphs, i.e. for α=1. The results were extended by [28] to include an upper bound of μ 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 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 is the neighborhood graph of a graph G and G is bipartite, then radG1radG and μG1μG or radG2radG and μG2μG where G1 and G2 are components of G. Also, if G is non-bipartite, radGradG and μGμG. 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.

Advertisement

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 G to be locally G [46], i.e. all vertices in G have neighborhoods that are isomorphic to the same graph G, given f:VGVG. Several questions regarding isomorphisms involving G which were raised by [35] including that of GG whenever G is either complete graph Kp,p2 or an odd cycle C2k+1,k1 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.

Advertisement

3. Basic definitions

A graphG=VE is a collection of ordered pairs of vertex set V=v1v2vn and edge set =vivj:vivjV, 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 Nv, 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, 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 (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 N1=234, N2=13,N3=12 and N4=1. Then by the definition of neighborhood graph G, we define edges in G via intersection of sets; N1N2=3, N1N3=2, N2N3=1, N1N4=, N2N4=1,N4N3=1. We then have two examples of G shown in Figure 2 (bottom).

Figure 1.

A tree.

Definition 3 [12]. Given a connected graph G with vertex set VG of order n, the distance between two vertices u,v of G, dGuv is defined as the length of the shortest uv path in G. Thus, diameter of G, diamG is the greatest distance among all pairs of vertices.

Definition 4 [15]. The radius of G, radG, is the minimum eccentricity of G where the eccentricity, ecGv, of a vertex vVG is the maximum distance between v and any other vertex in G. A vertex zVG is called central if ecGv=radG.

Definition 5 [28]. The average distanceμG of a connected graph G of order n is the average of distances between all pairs of vertices of G, i.e., μG=2uvdGuvnn1where dGuv denotes the distances between the vertices u and v in G.

Definition 6 [50]. The total distance of G is defined as dG=uvVGduv while the total distance of a vertex v is defined as dG=uVvduv.

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.

Advertisement

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 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 be its neighborhood graph. Consider G1 and G2 be two components of G. Then radG1radG and radG2radG.

Proof. Let G be a connected bipartite graph of radius r and let G be its neighborhood graph. Let VG1 and VG2 be two partitions of VG and G1 and G2 be two components of G.

Case 1: Let v0,v1VG1 such that G1 is the component of G. Since G is connected, then there exists a v0vr path between any two vertices v0,vrVG. Let v0v1v2vr1vr be a path connecting v0 and vr. But G is bipartite and so r1 must be odd. Then it follows that r is even. Since v1 is a common neighbor for v0 and v2, the two vertices v0 and v2 are adjacent in G. Similarly v2 is adjacent to v4,,vr2 is adjacent to vr in G. Thus dGv0vr=r2 since r is even. Therefore radG1radG.

Similarly, if v0,v1VG2 and G2 is the component of G, then radG2radG

Case 2: Let v0VG1 and vrVG2 and let G1 and G2 be two components of G By definition of neighborhood graph, these two vertices cannot be adjacent in G. If they were, there would exist a vertex u adjacent to both v0 and vr in G which could not be found in either VG1 and VG2 which is impossible. Thus the vertices from VG1 belong to one component, say G1 and those from VG2 to another component of G, say G2 and so radG1radG or radG2radG if v0,v1VG1 or v0,vrVG2. 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 be its neighborhood graph. Then radGradG,r1.

Proof. Let G be a connected non-bipartite graph and let G be its neighborhood graph. Then G contains an odd cycle. This cycle is also contained in G (see Alwardi et al., 2012). Let u1 and u2 be two adjacent vertices on the odd cycle of G. Let v0VG such that v0 is not equal to both u1 and u2. Let v0v1v2vr1vr be a path connecting v0 and vr. We consider two cases:

Case 1: Suppose r1 is odd. Then r is even. Let vr=u1 and v0u1u2. Using similar proof as in Theorem 1, Case 1, we get radGradG.

Case 2: Suppose r1 is even. Then r is odd. Then we have a path v0v1v2vr1vr connecting v0 and vr. Now let vr=u2. Thus, dGv0v2=r+12. Therefore, radGradG. 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 r1 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 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, dGvvr. Hence, the radius of G is r. But radG=r2 if r is even and radG=r2 if r is odd. Therefore, radGradG We note that radG=radG if G is the cycle C2r+1 since G is isomorphic to G (see [31]).

Figure 2.

Graph G (top) and its neighborhood graph G(bottom). Source (authors).

Proposition 3. Let G be a connected bipartite graph and let G be its neighborhood graph. Let G1 and G2 be two components of G. Then μG1μG and μG2μG. (Alternative to Proposition 5 and Corollary 1 discussed in Appendix 8.1).

Proof: we consider two cases.

Case 1: Let v0,vrVG1 and let G1 be the component of G. Since G is connected, then there is a path connecting v0 and vr. Let v0v1v2vr1vr be a path connecting v0 and vr. But G is bipartite and so r1 must be odd. It follows that r is even.

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

dGv=36n2+1+6n12n254E1

Now

dGv=1·n1+2·n2++r1·nr1+rnr
=1+2+3++rnrr12
=rr12+nrr2r12
=rn+r12rr12
dGv=r2n+2rr212E2

But, n=i=0rnir2r2. Hence

2nr2rE3

Without loss of generality, inequality [3] reduces to

2n+14r2r+14
2n+14r122
=2n+1412r12.

Hence,

r12+2n+1412=12+8n+12

We differentiate dGv in Eq. (2) w.r.t. r to get dGvdr=n32r2+2r12. Now, when drdv=0, we have

12n=3r2+4r
13+23n=r243r=r23249
19+23n=r232
19+23n12=r23

This implies that

r=23+1+6n3E4

Now dGv is maximized subject to the constraint r12+8n+12 for r=23+1+6n3. Then we get

dGv=36n2+1+6n12n254
dGv=18n1+1+6n6n127.E5

But

μG=1nn1vVdGv
=1nn1vV18n1+1+6n6n127.

So that,

μG=18n1+1+6n6n127nn1.E6

Now fix a vertex v in G1. For, i=0,1,2,r2, let ni be the number of vertices at distance i from v. We next show that

dG1v=18n2+1+3n6n+227E7

Now,

dG1v=1+2+3++r21+r2nrr14
=rr24+nr2r2r28
=2rr2+4nrr2r28
=2r24r+4nrr3+2r28
dG1v=4r24r+4nrr38E8

But, n=i=0rnirr24. Hence,

4nr22r
4n+1r12
4n+1r1
r1+4n+1

We differentiate dG1v in Eq. (8) to get

dvdr=188r4+4n3r2E9

Now, when dvdr=0, solving for r in Eq. (9), we get

r=4+12n+43.E10

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

dG1v=rr24+nr2r2r28
=4r24r+4nrr38
=r24r4r1n8
dG1v=r84nr22E11

Now, if dG1v in Eq. (11) is maximized subject to the constraint r1+4n+1 for r=4+12n+43, we get

dG1v=r84nr22
=4+23n+12424n8+83n+19
=18n2+6n+23n+127

Now, from the fact that μG1=1nn1vVdG1v, we have

μG1=18n2+6n+23n+127nn1E12

Since 18n1+6n16n+118n2+6n+23n+1, then we have μG1μG. Similarly, μG2μG. We conclude that μG1μG and μG2μG 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 be its neighborhood graph. Then, μGμG .

Proof. Let G be a connected non-bipartite graph. Then G contains an odd cycle. This cycle is also contained in G (see [31]). Let u1 and u2 be two adjacent vertices on the odd cycle of G. Let v0VG such that v0 is not equal to both u1 and u2. Let v0v1v2vr1vr be a path connecting v0 and vr. We consider two cases:

Case 1: Suppose r1 is odd. Then r is even. Let vr=u1. Using similar proof as in Proposition 3, we get μGμG.

Case 2: Suppose r1 is even. Then r is odd. Then we have a path v0v1v2vr1vr connecting v0 and vr. Now let vr=u2. Now that μG will be the same as in Proposition 3. We just need to determine μG.

Fix a vertex v in G. For, i=0,1,2,r2, let ni be the number of vertices at distance i from v. We show that

dGv=λ+18nλ2+2λ116.E13

Now, by its definition,

dGv=1+2+3++r+121+r+12nr218
=r218+r+12nr218
=r218+nr+12r+1r2116
=r2181r+12+nr+12
=2r22r3r2+r+116+nr+n2
=r2r1+r116+nr+n2
=1r2r1+8nr+116
dGv=r+18nr1216E14

But,

n=vVinir218
8nr21
r8n+1

We then differentiate dGv from Eq. (14) to get

dvdr=1168nr122r21.E15

Now, when dvdr=0 in Eq. (15), then 1168nr122r21=0 such that

r=1321+6n+1.E16

Further, if dGv of Eq. (14) is maximized, subject to the constraint r8n+1 for r=1321+6n+1, it can easily be shown that

dGv=r+18nr1216.E17

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

dGv=1321+6n+12+2321+6n+116E18

Let 1321+6n+1=λ in Eq. (18). Then we have

dGv=λ+18nλ2+2λ116.E19

Now, from the fact that μG=1nn1vVdG1v, we have

μG=1nn1vVdG1v=λ+18nλ2+2λ116nn1.E20

Since 18n1+1+6n6n127nn1λ+18nλ2+2λ116nn1, we have μGμG 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 μGαG where αG denotes the independent number of the graph G [27], then for the corresponding neighborhood graph G, it also follows that μGαG and αGαG.

4.2 Simulation results

In this section, we present a simulation of our key results, i.e. μG1μG and μGμG . 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.

Advertisement

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.

Advertisement

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 vi and it’s neighborhood Ni defined by Ni=vj:eijEejiE, let ki be defined as the number of vertices,Ni, in the neighborhood, Ni of a vertex. The local clustering coefficient Ci for a vertex vi 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, Ci for the directed and undirected graphs would, respectively be described by

Ci=ejk:vjvkNiejkEkiki1andCi=2ejk:vjvkNiejkEkiki1E21

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, but both having same species [40]. Therefore, the relationship between average distance of two graphs G and G 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.

Advertisement

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 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 γ-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 γ-neighborhood graphs.

Secondly, just as with γ-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].

Advertisement

Acknowledgments

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

Advertisement

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.

Advertisement

A.1 Alternative proofs

Proof of proposition 1.

Let eiRn be a basis, and DG be the distance matrix for graph G. Then by the definition of eccentricity, ecGi=maxeiTDG of vertex i. Similarly, the definition of radius implies that radG=minmaxeiTDG:i=123n. Since G is connected, then there are nn12 graph geodesics in G. That is, that there are nn1 non-zero entries in DG. But G is bipartite, then, it has two sets of vertices V1 and V2 which belong to the components GNt, for t=1,2. Further, by definition of neighborhood graph, it follows then that V1+V2=n, such that V1,V2<n. This means each graph geodesic in the components is of length less than that of G.

Without loss of generality, let VtVt12 be the graph geodesic for each component GNt. This implies that the number of non-zero components in GNt is VtVt1<nn1 . Therefore,

eiTDGNtejeiTDGej
t=1,2;maxeiTDGNtmaxeiTDG
minmaxeiTDGNt:i=123VtminmaxeiTDG:i=123n

Therefore, radGNtradG .

Proof of proposition 2.

Let G be a connected non-bipartite graph and let G be its neighborhood graph with their respective distance matrices DG and DG. By definition of neighborhood graph, thenG is also connected and non-bipartite [31]. Thus, both G and G contain an odd cycle [49, 59]. In particular, both G and G have the same odd cycle [31]. Let u1 and u2 be two adjacent vertices on the odd cycle of G. Let C2k+1,kN be such a cycle. We consider two cases:

Case 1: Suppose G=C2k+1. Then accordingly, G=C2k+1=G such that DG=DG . In particular, GG (see [44], Theorems 4 and 5). Using similar proof as in Theorem 1, we have

minmaxeiTDG:i=122k+1minmaxeiTDG:i=122k+1,

such that we get radG=radG.

Case 2: Suppose GC2k+1. Let v0v1v2vr1vrvr+1vr+2 be a path connecting v0 and vr+2 on the cycle C2k+1 in G. Let us consider then any two arbitrary vertices u1 and ur not in C2k+1 but available in G. Further let v0VC2k+1 such that uru1v0 is a path in G because G is connected. Suppose v0=vj+1. Then by definition of neighborhood graph, u1 is adjacent to vj and vj+2 contained in G. This means that every path uru1v0 is reduced by at least one edge length in order to form the graph G. Thus, the length of graph geodesics in G are always lower than those in G. Then,

eiTDGejeiTDGej
i=1,2,,n;maxeiTDGmaxeiTDG
minmaxeiTDG:i=123nminmaxeiTDG:i=123n

Therefore, radGradG. Now, the simplest non-bipartite graph is G=C2k+1 where radG=k1 because ,kN. This completes the proof.

Proposition 5. Let G be a neighborhood of a connected bipartite graph G. Let Gt,t=1,2 be two components of G. Then

μGtnn1μGVtVt1,t=1,2E22

Proof. Let G be the neighborhood graph of a bipartite graph G and both simple. Further, suppose Gt,t=1,2 are the two components of G. Then eiTDGtei=0,i=1,2,,Vt . Likewise, eiTDGei=0,i=1,2,,n for the graph G. Then,

2uvEGdGuv=i=1nj=1neiTDGejand2uvEGdGtuv=i=1nj=1neiTDGtej.

We have already shown, previously, that eiTDGtejeiTDGej . Then, we may proceed to say that

i=1nj=1neiTDGteji=1nj=1neiTDGej,

which also implies that

2uvEGdGtuv2uvEGdGuv.E23

If we divide the inequality [23] by nn1>0 both sides, we have,

2uvEGdGtuvnn12uvEGdGuvnn1.E24

The RHS of inequality [24] is equal to μG. Also, by construction, we have

VtVt1μGtnn1μG.E25

Inequality [25] means that

μGtnn1μGVtVt1.E26

Corollary 1. Let G be a neighborhood of a connected bipartite graph G such that Gt,t=1,2 are the two components of G. Then, if

μGtnn1μGVtVt1,t=1,2E27

then δμGt<μG,t=1,2 whenever VtVt1<nn1. Consequently, for an infinitely small δ>0, for n,μGt<μG,t=1,2. Moreover this result is also true given that Vt is the neighborhood number of Gt (see [33, 43]).

Proof of proposition 4.

Let G be its neighborhood graph of a connected non-bipartite graph G be and with their respective distance matrices DG and DG.

By Corollary 1, we have already shown that for a bipartite neighborhood graph Gt,having two components G1 and G2,

μGtnn1μGVtVt1,t=1,2.E28

In general, if G is non-partitioned, for all t=1,2, VtVt1=nn1. Then, the inequality [28] reduces to μGμG.

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

Neighborhood graph

μ.

Average distance of

d.

Total distance of or geodesic distance

d..

Distance between two vertices

V.

Vertex set of

rad.

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

k.

Sum of numbers indexed by k

λ

Parameter for the characteristic equation

v

Vertex

dGv

Shortest distance of vertex v from central vertex in a graph

G.

Bipartite graphs

ecGv

Maximum distance of vertex v from any other vertex

diam.

Diameter of graph or maximum eccentricity

E.

Set of edges

Isomorphism

Vt

Cardinality or number of elements

Less than or equal to

<

Strictly less than

Infinity or larger number

eiT

Transpose of ei

Cp

Cycle of length p

Kp

Complete graph with p number of vertices

α

Independent number of a graph

References

  1. 1. Uganda J, Karrer B, Backstrom L, Marlow C. The anatomy of the Facebook social graph. 2011
  2. 2. Jain A, Reddy BVR. Node centrality in wireless sensor networks: Importance, applications and advances. In: 2013 3rd IEEE International Advance Computing Conference (IACC). IEEE; 2013. p. 127–31
  3. 3. Qiao T, Shan W, Zhou C. How to identify the most powerful node in complex networks? A novel entropy centrality approach. Entropy. 2017;19(11):614
  4. 4. García-Gonzalez E, Chimal-Eguia JC, Mario E. Rivero-Angeles VP. On the Use of Graphs for Node Connectivity in Wireless Sensor Networks for Hostile Environments. J Sensors [Internet]. 2019;2019:22. Available from: https://doi.org/10.1155/2019/7409329
  5. 5. Cozzens M. Food webs, competition graphs, and habitat formation. Math Model Nat Phenom. 2011;6:22–38
  6. 6. Mwakilama E, Eneya L. A transport optimization model for retail distribution: A case study of Zomba bakery. In: Kumwenda K, Chisala B, editors. Proceedings of the 30th international conference on mathematical sciences association (SAMSA). Lilongwe: SAMSA 2013; 2013. p. 111–9
  7. 7. Detofeno T. Optimizing routes for collection of urban waste: A case study for the city of Joinville, Sate of Santa Catarina. J Ind Eng. 2010;2(1):124–36
  8. 8. Desai N, Vashi B. Optimization and privatization of city bus network using GIS: A case study of Vadodara city in Gujarat state. 2008
  9. 9. Hali K. A multiperiod set covering location model for dynamic redeployment of ambulances. Comput Oper Res. 2008;35:814–36
  10. 10. Jia H, Ordonez F, Dessouky M. A modeling framework for facility location of medical services for large-scale emergencies. IIE Trans. 2007;39:41–5
  11. 11. Roberts F. Discrete mathematical models, with applications to social, biological, and environmental problems. New Jersey: Prentice-Hall, Inc., Englewood Cliffs.; 1976
  12. 12. Ye Q, Wu B, Wang B. Distance Distribution and Average Shortest Path Length Estimation in Real-world Networks. In: Cao L, Feng Y, Zhong J, editors. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 2010. p. 1–12
  13. 13. Levenkova N. Applications of graph theory to real-world networks [Internet]. UNSW-Australia; 2014. Available from: http://unsworks.unsw.edu.au/fapi/datastream/unswork
  14. 14. Wang Y, Yuan Y, Ma Y, Wang G. Time-Dependent Graphs: Definitions, Applications, and Algorithms. Data Sci Eng [Internet]. 2019;4(4):352–66. Available from: https://doi.org/10.1007/s41019-019-00105-0
  15. 15. Morzy M, Kajdanowicz T. Graph energies of egocentric networks and their correlation with vertex centrality measures. Entropy. 2018;20(12):1–18
  16. 16. Newman MEJ, Strogatz SH, Watts DJ. Random graphs with arbitrary degree distributions and their applications. Phys Rev E - Stat Physics, Plasmas, Fluids, Relat Interdiscip Top. 2001;64(2):17
  17. 17. Althöfer I. Average distances in undirected graphs and the removal of vertices. J Comb Theory Ser B [Internet]. 1990;48(1):140–2. Available from: https://doi.org/10.1016/0095-8956(90)90136-N
  18. 18. Bienstock D, Gyon E. Average distance in graphs with removed elements. J Graph Theory. 1988;12:375–90
  19. 19. Dankelmann P. Computing the average distance of an interval graph. Inf Process Lett [Internet]. 1993;48(6):311–4. Available from: https://doi.org/10.1016/0020-0190(93)90174-8
  20. 20. Erdös P, Pach J, Spencer J. CONGRESSUS NUMERANTIUM 64(1988), pp .121-124. 1988;64:121–4
  21. 21. Winkler P. Mean distance and the ‘four-thirds conjecture.’ Congr Numer. 1986;54:63–72
  22. 22. Winkler P. Mean distance in a tree. Discret Appl Math. 1990;27:179–85
  23. 23. Mohar B. Eigenvalues, diameter, and mean distance in graphs. Graphs Comb. 1991;7:53–64
  24. 24. Bekkai S, Kouider M. On mean distance and girth. Discret Appl Math [Internet]. 2010;158(17):1888–1893. Available from: doi:https://doi.org/10.1016/j.dam.2010.06.013
  25. 25. Favaron O, Kouider M, Mahéo M. Edge-vulnerability and mean distance. Networks [Internet]. 1989;19:493–504. Available from: https://doi.org/10.1002/net.3230190502
  26. 26. Saha A. Computation of average distance, radius and centre of a circular-arc graph in parallel. J Phys Sci. 2006;10:178–87
  27. 27. Chung FRK. The average distance and the independence number. J Graph Theory [Internet]. 1988;12:229–35. Available from: https://doi.org/10.1002/jgt.3190120213
  28. 28. Dankelmann P. Average Distance and Independence number. Discret Appl Math. 1994;51:75–83
  29. 29. Dankelmann P. Average distance and domination number. Discret Appl Math. 1997;80:75–83
  30. 30. Dundar P, Aytac A, Kilic E. Common-neighbourhood of a graph. Bol da Soc Parana Mat. 2017;35(1):23–32
  31. 31. Alwardi A, Arsić B, Gutman I, Soner ND. The common neighborhood graph and its energy. Iran J Math Sci Informatics. 2012;7(2):1–8
  32. 32. Veltkamp RC. The γ-neighborhood graph. Comput Geom Theory Appl. 1992;1(4):227–46
  33. 33. Sampathkumar E, Neeralagi PS. The neighbourhood number of a graph. Vol. 16, Indian J. Pure Appl. Math. 1985. p. 126–32
  34. 34. Brigham R, Dutton R. On neighborhood graphs. J Comb Inf Syst Sci. 1987;12
  35. 35. Acharya BD, Vartak MN. Open neighbourhood graphs. Bombay-40O 076; 1973
  36. 36. Hell P. Graphs with given neighborhoods I. Problèmes Comb théorie des graphes, Colloq Int CNRS. 1978;260:219–23
  37. 37. Nayaka SR, Purushothama S. The Open Neighborhood Number of a Graph. 2017;1(6):52–4
  38. 38. Supowit KJ. The relative neighbourhood graph with an application to minimum spanning trees. J ACM [Internet]. 1983;30:428 – 447. Available from: https://dl.acm.org/doi/10.1145/2402.322386
  39. 39. Toussaint GT. The relative neighbourhood graph of a finite planar set. Pattern Recognit. 1980;12(4):261–8
  40. 40. Roberts F. Food webs, competition graphs, and the boxicity of ecological phase space. In: Roberts F, editor. Theory and Applications of graphs. New Jersey: Proceedings, Michigan University; 1978. p. 447–90
  41. 41. Fajtlowicz S. On conjectures of Graffiti. Discrete Math. 1988;72(1–3):113–8
  42. 42. Tian F, Xu J. Average distance and independence number. Discret Appl Math. 2009;157:1113–27
  43. 43. Chaluvaraju B. Some Parameters on Neighborhood Number of A Graph. Electron Notes Discret Math [Internet]. 2009;33(C):139–46. Available from: http://dx.doi.org/10.1016/j.endm.2009.03.020
  44. 44. Brigham RC, Dutton RD. On neighborhood graphs. J Comb Inf Syst Sci. 1987;12(1–2):75–84
  45. 45. Dehmer M. Structural analysis of complex networks. Struct Anal Complex Networks. 2011;(October 2010):1–486
  46. 46. Sedláček J. On local properties of finite graphs. Graph Theory, Lagów, Lect Notes Math. 1983;1018:242–247
  47. 47. Kulli VR. The neighborhood graph of a graph. Int J Fuzzy Math Arch. 2015;8(October):93–9
  48. 48. Mukwembi S. Average Distance, Independence Number, and Spanning Trees. J Graph Theory. 2014;76
  49. 49. West DB. Introduction to Graph Theory. 2nd ed. Upper Saddle River: Prentice-Hall, Inc.,; 2001
  50. 50. Dankelmann P, Mukwembi S. The distance concept and distance in graphs. Distance Mol graphs--theory, Univ Kragujevac, Kragujev. 2012;3–48
  51. 51. Gao XL, Xu SJ. Average Distance , Connected Hub Number and Connected Domination Number. 2019;82:57–75
  52. 52. Quadras J, Christy KAS, Nelson A, Sarah S. Average Distance of Certain Graphs. Int J Math its Appl. 2017;5(1):373–81
  53. 53. Firby P, Haviland J. Independence and average distance in graphs. Discret Appl Math. 1997;75(1):27–37
  54. 54. Cai W, Snyder J, Hastings A, D’Souza RM. Mutualistic networks emerging from adaptive niche-based interactions. Nat Commun [Internet]. 2020;11(1):1–10. Available from: http://dx.doi.org/10.1038/s41467-020-19154-5
  55. 55. Jordi B, Pedro J. Plant-Animal Mutualistic Networks: The Architecture of Biodiversity. Annu Rev Ecol Evol Syst. 2007;38(1):567–93
  56. 56. Bascompte J, Jordano P, Melián CJ, Olesen JM. The nested assembly of plant-animal mutualistic networks. Proc Natl Acad Sci U S A. 2003;100(16):9383–7
  57. 57. Nagaishi E, Takemoto K. Network resilience of mutualistic ecosystems and environmental changes: An empirical study. R Soc Open Sci. 2018;5(9)
  58. 58. Feng W, Takemoto K. Heterogeneity in ecological mutualistic networks dominantly determines community stability. Sci Rep. 2014;4:1–11
  59. 59. Konig D. Theorie der endlichen und unendlichen Graphen. Akad: Verlagsges., Leipzig; 1936

Written By

Elias Mwakilama, Patrick Ali, Patrick Chidzalo, Kambombo Mtonga and Levis Eneya

Submitted: 21 May 2021 Reviewed: 19 June 2021 Published: 27 September 2021