Open access peer-reviewed chapter - ONLINE FIRST

On Average Distance of Neighborhood Graphs and Its Applications

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

Submitted: April 21st 2021Reviewed: June 19th 2021Published: September 27th 2021

DOI: 10.5772/intechopen.98986

Downloaded: 24

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 Gof a graph Ghas the same vertex set as G, that is, VG=VG, and two vertices u, vare adjacent in Gif and only if they have a common neighbor in G(if and only there exists a path of length 2 between uand vin G). Thus, the neighborhood of a vertex vin a graph Gis the subgraph of Gdenoted by Gand induced by all vertices adjacent to v[34]. Hence, the graph Gcomprises the vertices adjacent to vand 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αGposed 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 Gsuch that the neighborhood graph Gis 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 Gis the neighborhood graph of a graph Gand Gis bipartite, then radG1radGand μG1μGor radG2radGand μG2μGwhere G1and G2are components of G. Also, if Gis non-bipartite, radGradGand μ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 Gto be locally G[46], i.e. all vertices in Ghave neighborhoods that are isomorphic to the same graph G, given f:VGVG. Several questions regarding isomorphisms involving Gwhich were raised by [35] including that of GGwhenever Gis either complete graph Kp,p2or an odd cycle C2k+1,k1have 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=VEis a collection of ordered pairs of vertexset V=v1v2vnand edgeset =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 subgraphof a graph is some smaller portion of that graph. Further, an induced (generated) subgraphis 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 vand all of its neighbors; sometimes referred to as the closed neighborhoodof v.

The neighborhood graph of G, in general, denoted by G, refers therefore to the graph with the same vertex set as Gin 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.

Figure 1.

A tree.

For example, given a graph Gin Figure 1 (top), we first construct the open neighborhood sets for each corresponding vertices as N1=234, N2=13,N3=12and N4=1. Then by the definition of neighborhood graph G, we define edges in Gvia intersection of sets; N1N2=3, N1N3=2, N2N3=1, N1N4=, N2N4=1,N4N3=1. We then have two examples of Gshown in Figure 2 (bottom).

Definition 3[12]. Given a connected graph Gwith vertex set VGof order n, the distance between two vertices u,vof G, dGuvis defined as the length of the shortest uvpath in G. Thus, diameter of G, diamGis the greatest distance among all pairs of vertices.

Definition 4[15]. The radiusof G, radG, is the minimum eccentricity of Gwhere the eccentricity, ecGv, of a vertex vVGis the maximum distance between vand any other vertex in G. A vertex zVGis called centralif ecGv=radG.

Definition 5[28]. The average distanceμGof a connected graph Gof order nis the average of distances between all pairs of vertices of G, i.e., μG=2uvdGuvnn1where dGuvdenotes the distances between the vertices uand vin G.

Definition 6[50]. The total distance of Gis defined as dG=uvVGduvwhile the total distance of a vertex vis defined as dG=uVvduv.

Definition 7[49]. A graph Gis bipartiteif its vertex set can be partitioned into sets Uand Vin such a way that every edge of Ghas one end vertex in Uand the other in V. In this case, Uand Vare called partitesets.

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, Gis bipartite. We first show that if Gif bipartite, then the radius of each component of the neighborhood graph of Gcannot exceed the radius of G.

Proposition 1. Let Gbe a connected bipartite graph and let Gbe its neighborhood graph. Consider G1and G2be two components of G. Then radG1radGand radG2radG.

Proof. Let Gbe a connected bipartite graph of radius rand let Gbe its neighborhood graph. Let VG1and VG2be two partitions of VGand G1and G2be two components of G.

Case 1: Let v0,v1VG1such that G1is the component of G. Since Gis connected, then there exists a v0vrpath between any two vertices v0,vrVG. Let v0v1v2vr1vrbe a path connecting v0and vr. But Gis bipartite and so r1must be odd. Then it follows that ris even. Since v1is a common neighbor for v0and v2, the two vertices v0and v2are adjacent in G. Similarly v2is adjacent to v4,,vr2is adjacent to vrin G. Thus dGv0vr=r2since ris even. Therefore radG1radG.

Similarly, if v0,v1VG2and G2is the component of G, then radG2radG

Case 2: Let v0VG1and vrVG2and let G1and G2be two components of GBy definition of neighborhood graph, these two vertices cannot be adjacent in G. If they were, there would exist a vertex uadjacent to both v0and vrin Gwhich could not be found in either VG1and VG2which is impossible. Thus the vertices from VG1belong to one component, say G1and those from VG2to another component of G, say G2and so radG1radGor radG2radGif v0,v1VG1or v0,vrVG2. This concludes the proof.

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

Proposition 2. Let Gbe a connected non-bipartite graph and let Gbe its neighborhood graph. Then radGradG,r1.

Proof. Let Gbe a connected non-bipartite graph and let Gbe its neighborhood graph. Then Gcontains an odd cycle. This cycle is also contained in G(see Alwardi et al., 2012). Let u1and u2be two adjacent vertices on the odd cycle of G. Let v0VGsuch that v0is not equal to both u1and u2. Let v0v1v2vr1vrbe a path connecting v0and vr. We consider two cases:

Case 1: Suppose r1is odd. Then ris even. Let vr=u1and v0u1u2. Using similar proof as in Theorem 1, Case 1, we get radGradG.

Case 2: Suppose r1is even. Then ris odd. Then we have a path v0v1v2vr1vrconnecting v0and 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 Tbe a tree (Figure 1) such that every leaf of Tis of radius r1from the central vertex. Connect any two leaves to obtain Gfrom T. Let xbe the central vertex of Tand let vand vbe two leaves which are adjacent in G. This pair of vertices is contained in a cycle of length at most 2r+1in G. Thus, dGvvr. Hence, the radius of Gis r. But radG=r2if ris even and radG=r2if ris odd. Therefore, radGradGWe note that radG=radGif Gis the cycle C2r+1since Gis isomorphic to G(see [31]).

Figure 2.

GraphG(top) and its neighborhood graphG(bottom). Source (authors).

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

Proof: we consider two cases.

Case 1: Let v0,vrVG1and let G1be the component of G. Since Gis connected, then there is a path connecting v0and vr. Let v0v1v2vr1vrbe a path connecting v0and vr. But Gis bipartite and so r1must be odd. It follows that ris even.

Fix a vertex vin G. For i=0,1,2,,r, let nibe the number of vertices at distance ifrom 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 dGvin Eq. (2) w.r.t. rto 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 dGvis maximized subject to the constraint r12+8n+12for 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 vin G1. For, i=0,1,2,r2, let nibe the number of vertices at distance ifrom 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 dG1vin Eq. (8) to get

dvdr=188r4+4n3r2E9

Now, when dvdr=0, solving for rin 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 dG1vin Eq. (11) is maximized subject to the constraint r1+4n+1for 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μGand μG2μGas 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 Gbe a connected non-bipartite graph and let Gbe its neighborhood graph. Then, μGμG.

Proof. Let Gbe a connected non-bipartite graph. Then Gcontains an odd cycle. This cycle is also contained in G(see [31]). Let u1and u2be two adjacent vertices on the odd cycle of G. Let v0VGsuch that v0is not equal to both u1and u2. Let v0v1v2vr1vrbe a path connecting v0and vr. We consider two cases:

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

Case 2: Suppose r1is even. Then ris odd. Then we have a path v0v1v2vr1vrconnecting v0and vr. Now let vr=u2. Now that μGwill be the same as in Proposition 3. We just need to determine μG.

Fix a vertex vin G. For, i=0,1,2,r2, let nibe the number of vertices at distance ifrom 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 dGvfrom Eq. (14) to get

dvdr=1168nr122r21.E15

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

r=1321+6n+1.E16

Further, if dGvof Eq. (14) is maximized, subject to the constraint r8n+1for 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μGas 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 non its upper bound as procedure described in [28].

Conjecture 1. Given a graph Gsuch that μGαGwhere αGdenotes the independent number of the graph G[27], then for the corresponding neighborhood graph G, it also follows that μGαGand αGαG.

4.2 Simulation results

In this section, we present a simulation of our key results, i.e. μG1μGand μ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 viand it’s neighborhood Nidefined by Ni=vj:eijEejiE, let kibe defined as the number of vertices,Ni,in the neighborhood, Niof a vertex. The local clustering coefficient Cifor a vertex viis 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, Cifor 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 Gand a disturbed network G, but both having same species [40]. Therefore, the relationship between average distance of two graphs Gand Gdeduced 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 Gand graph Gwas 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 eiRnbe a basis, and DGbe the distance matrix for graph G. Then by the definition of eccentricity, ecGi=maxeiTDGof vertex i. Similarly, the definition of radius implies that radG=minmaxeiTDG:i=123n. Since Gis connected, then there are nn12graph geodesics in G. That is, that there are nn1non-zero entries in DG. But Gis bipartite, then, it has two sets of vertices V1and V2which 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 VtVt12be the graph geodesic for each component GNt. This implies that the number of non-zero components in GNtis VtVt1<nn1. Therefore,

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

Therefore, radGNtradG.

Proof of proposition 2.

Let Gbe a connected non-bipartite graph and let Gbe its neighborhood graph with their respective distance matrices DGand DG. By definition of neighborhood graph, thenGis also connected and non-bipartite [31]. Thus, both Gand Gcontain an odd cycle [49, 59]. In particular, both Gand Ghave the same odd cycle [31]. Let u1and u2be two adjacent vertices on the odd cycle of G. Let C2k+1,kNbe such a cycle. We consider two cases:

Case 1: Suppose G=C2k+1. Then accordingly, G=C2k+1=Gsuch 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+2be a path connecting v0and vr+2on the cycle C2k+1in G. Let us consider then any two arbitrary vertices u1and urnot in C2k+1but available in G. Further let v0VC2k+1such that uru1v0is a path in Gbecause Gis connected. Suppose v0=vj+1. Then by definition of neighborhood graph, u1is adjacent to vjand vj+2contained in G. This means that every path uru1v0is reduced by at least one edge length in order to form the graph G. Thus, the length of graph geodesics in Gare 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+1where radG=k1because ,kN. This completes the proof.

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

μGtnn1μGVtVt1,t=1,2E22

Proof. Let Gbe the neighborhood graph of a bipartite graph Gand both simple. Further, suppose Gt,t=1,2are the two components of G. Then eiTDGtei=0,i=1,2,,Vt. Likewise, eiTDGei=0,i=1,2,,nfor 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>0both 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 Gbe a neighborhood of a connected bipartite graph Gsuch that Gt,t=1,2are the two components of G. Then, if

μGtnn1μGVtVt1,t=1,2E27

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

Proof of proposition 4.

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

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

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

In general, if Gis 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 vfrom central vertex in a graph

G.

Bipartite graphs

ecGv

Maximum distance of vertex vfrom 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 pnumber of vertices

α

Independent number of a graph

DOWNLOAD FOR FREE

chapter PDF

© 2021 The Author(s). Licensee IntechOpen. This chapter is distributed under the terms of the Creative Commons Attribution 3.0 License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

How to cite and reference

Link to this chapter Copy to clipboard

Cite this chapter Copy to clipboard

Elias Mwakilama, Patrick Ali, Patrick Chidzalo, Kambombo Mtonga and Levis Eneya (September 27th 2021). On Average Distance of Neighborhood Graphs and Its Applications [Online First], IntechOpen, DOI: 10.5772/intechopen.98986. Available from:

chapter statistics

24total chapter downloads

More statistics for editors and authors

Login to your personal dashboard for more detailed statistics on your publications.

Access personal reporting

We are IntechOpen, the world's leading publisher of Open Access books. Built by scientists, for scientists. Our readership spans scientists, professors, researchers, librarians, and students, as well as business professionals. We share our knowledge and peer-reveiwed research papers with libraries, scientific and engineering societies, and also work with corporate R&D departments and government entities.

More About Us