# Connectivity and Wiener Index of Fuzzy Incidence Graphs

Authors: Juanyan Fang; Irfan Nazeer; Tabasam Rashid; Jia-Bao Liu
Journal: Mathematical Problems in Engineering
 (2021)

---

## Abstract

Connectivity is a key theory in fuzzy incidence graphsFIGs. In this paper, we introduced connectivity index CI, average connectivity index ACI, and Wiener index WI of FIGs. Three types of nodes including fuzzy incidence connectivity enhancing node FICEN, fuzzy incidence connectivity reducing node FICRN, and fuzzy incidence connectivity neutral node FICNN are also discussed in this paper. A correspondence between WI and CI of a FIG is also computed.


---

## Body

## 1. Introduction and Preliminaries

Zadeh [1] presented the theory of fuzzy set FS to resolve complications in tackling with precariousness. Since then, the FS theory becomes a rich area in multiple disciplines, including mathematics, computer science, and signal processing. The theory of graphs has been considered to play a vital role in dealing with real-life situations. A graph is an easy way of expressing information, including the relationship between different objects. The objects are shown by nodes, and relations are represented by edges. In this paper, all graphs are finite, simple, without loops, and undirected. When there is a lack of certainty in the illustration of the objects and their association, we need to draw a fuzzy graph FG model. Zadeh’s FS provided a productive ground for the theory of FGs which has been proposed by Rosenfeld [2]. In a graph, the strength of connectedness SC between any two vertices is either 0 or 1, whereas in FG, it is a real number ∈0,1. The study of FGs leads many scientists to contribute in this field, such as Yeh and Bang [3] studied the concept of FGs independently and discussed its applications in clustering analysis. Bhattacharya and Suraweera [4] discussed an algorithm to compute the max-min powers and property of FGs. Bhutani [5] worked on automorphism of FGs. Mordeson [6] introduced fuzzy line graphs. Bhutani and Rosenfeld [7, 8] studied strong arcs as well as fuzzy end nodes in FGs. Sunitha and Vijayakumar [9, 10] defined fuzzy trees and fuzzy blocks in FGs. Samanta et al. [11] inaugurated completeness and regularity of generalized FGs. Samanta and Pal [12] studied fuzzy planner graphs. Mathew and Sunitha [13] classified the edges of a FG as an α−strong,β−strong, and δ−edge. Mathew and Sunitha [14, 15] presented vertex, edge connectivity, and cycle connectivity in FGs. Mathew et al. [16] initiated saturation in FGs, and Binu et al. [17] explored CI and its application in FGs. Binu et al. [18] investigated CI of FG and its application to human trafficking. For some other significant works on graphs and FGs, one may refer to [19–25].Wiener [26] was the first who investigated WI when he was studying about the boiling point of paraffin. After the landmark work of Harold Wiener about WI, in the middle of 1970s, new results related to WI were described. In graphs, WI has been studied in different fields such as Chemistry, Mathematics, and Physics. Binu et al. [27] discussed WI of FG and its application to illegal immigration networks.FGs are unable to provide any information on the effect of a vertex on edges of the graph. Therefore, this disadvantage opens a way to introduce FIGs. FIGs talk about the effect of a vertex on an edge. Dinesh [28] presented the idea of FIGs. For example, if vertices show different residence societies and edges show roads joining these residence societies, we can have a FG expressing the extent of traffic from one society to another. The society has the maximum number of residents and will have maximum ramps in society. So, if c and d are two societies and cd is a road joining them, then c,cd could express the ramp system from the road cd to the society c. In the case of an unweighted graph, c and d both will have an influence of 1 on cd. In a directed graph, the influence of c on cd represented by c,cd is 1, whereas d,cd is 0. This idea can be generalized by FIGs. Mordeson [29] studied numerous connectivity perceptions in FIGs. Malik et al. [30] explained different uses of FIGs. Mordeson et al. [31] proposed a fuzzy incidence HTML translation failed blocks along with their applications. Mordeson and Mathew [32] discussed different connectivity ideas in FIGs.The motivation of our work is thatCI, ACI, and WI of FGs exists in literature, but these indices are unknown for FIGs. These indices will make a way to study different properties of FIGs at length. This is why we propose these concepts for FIGs. Our work will open the new doors for many researchers to study FIGs in detail. The outline of this paper is as follows. In Section 1, we provide elementary definitions, results, and expressions of FIGs, which are required for the development of the content. In Section 2, we discuss CI of FIGs. Section 3 describes certain boundaries for CI of FIGs. CI of vertex and edge deleted fuzzy incidence subgraph FIS is illustrated in Section 4. Section 5 explains ACI and its characteristics. In Section 6, we discuss WI of FIG and a relationship between connectivity and WI. Below, we present some preliminary definitions from [17, 19, 32].LetG be a simple graph with vertex set VG and edge set EG. Then, an incidence graph IG is given by G=V,E,I, where I⊆V×E. An IG is shown in Figure 1, and if u,uv is in IG, then u,uv is said to be an incidence pair or pair. Assume an IGG=V,E,I. A sequence v0,v0,v0v1,v0v1,v1,v0v1,v1,…,vn−1, vn−1,vn−1vn,vn−1vn,vn,vn−1vn,vn is said to be a walk. It is closed if v0=vn. A walk is called a path if it has all distinct vertices. An IG is said to be connected if all pair of vertices are joined by a path. An edge ab is said to be a fuzzy bridge FB if the deletion of ab∈θ∗ lessens the SC between some pair of vertices in G.Figure 1
Incidence graph.In this paper, minimum is represented by∧ and maximum is expressed by ∨.Definition 1.
Consider a graphG=V,E, and η and θ are fuzzy subsets of V and E, respectively. Assume V×E has a fuzzy subset ψ. If ψv∗,e∗≤ηv∗∧θe∗ for every v∗∈V and e∗∈E, then ψ is called a FI of G.Definition 2.
Assume a graphG=V,E and η,θ be a fuzzy subgraph of G, if ψ is a FI of G, then G=η,θ,ψ is called a FIG of G.Definition 3.
Consider aFIGG=η,θ,ψ. Then, H=κ,ϕ,Ω is a FIS of G if κ⊆η,ϕ⊆θ and Ω⊆ψ.Definition 4.
AssumeG=η,θ,ψ is a FIG. A FI path λ from g to h, g,gh∈η∗∪θ∗, is defined as a sequence of elements η∗,θ∗, and ψ∗ beginning with g and closing with h. The minimum value of ψx,xy is called incidence strength IS, where x,xy∈λ.InFIG, the incidence paths IPs can take distinct forms. u0=u0,u0u1,u0u1 is an IP of length one. u0=u0,u0u1,u0u1,u1,u0u1u1 is an IP of length two.Definition 5.
ConsiderG be a FIG. An incidence pair a,ab is strong if ψa,ab≥ICONNG−a,aba,ab where ICONNG−a,aba,ab shows the highest IS of a−ab. If ψa,ab>ICONNG−a,aba,ab, then the pair is called α−strong. If ψa,ab=ICONNG−a,aba,ab, then this type of pair is β−strong. If an incidence pair is α−strong or β−strong, then this kind of pair is a strong pair. If HTML translation failed, then this type of pair is called δ−incidence pair.Definition 6.
AssumeG be a FIG. If all pairs of λ are strong, then an IPλ in G is called strong IP.Definition 7.
ConsiderG=η,θ,ψ be a FIG. H=κ,ϕ,Ω is called a subgraph of G if κa=ηa for all a∈κ∗, ϕab=θab for all ab∈ϕ∗, and Ωa,ab=ψa,ab for all pair a,ab∈Ω∗.Proposition 1.
IfH is a FIS of G, then ICONNHa,ab≤ICONNGa,ab.Definition 8.
AFIG of G is said to be complete if ψa,ab=ηa∧θab for every a,ab∈ψ∗.Definition 9.
(see [19]). The distance du,v between two vertices u,v∈VG is the minimum number of edges in a path between u and v in G.Definition 10.
In a graphG, a path of shortest length is called geodesic.Definition 11.
(see [19]). WI of a graph G is the sum of distances between all pairs of vertices of G. Then, the WI of a graph G is given by WG=∑u,v∈VGdu,v.


## 2. Connectivity Index of Fuzzy Incidence Graph

Connectivity is a common parameter associated with a network. This section includes the introduction and formula to calculateCI of FIG. For easiness, in the coming sections, we will take ηa=1 for every a∈η∗.Definition 12.
LetG=η,θ,ψ be a FIG. The CI of G is given by(1)CIG=∑a,b∈η∗ηaηbICONNGa,b,ICONNGa,b is the maximum value of ISs for all the possible IPs between a and b.Example 1.
AssumeG is a FIG given in Figure 2 having η∗=i,j,k,l; θij=0.8,θik=0.4,θjk=0.7,θkl=0.9;ψi,ij=0.7,ψj,ji=0.5,ψi,ik=0.3,ψk,ki=0.2,ψj,jk=0.3,ψk,kj=0.7,ψk,kl=0.7, and ψl,lk=0.3 with CIG=2.0.Figure 2
A fuzzy incidence graph withCI=2.0.The connectivity indices of subgraphs ofFIGs can never be surpassed that of the FIGs. Therefore, a subgraph H of FIGG will have to be less than or equal to CI than the CIG. This is shown in the coming proposition.Proposition 2.
IfH=κ,ϕ,Ω is a FIS of G=η,θ,ψ, then CIH≤CIG.Proof.
Leta,b∈κ∗. As H=κ,ϕ,Ω is a FIS of G=η,θ,ψ, κa≤ηa. Also, if H is a FIS of G, then ICONNHa,b≤ICONNGa,b for any two a,b∈κ∗. This implies ∑a,b∈κ∗κaκbICONNHa,b≤∑a,b∈η∗ηaηbICONNGa,b which implies CIH≤CIG.Example 2.
ConsiderG be a FIG provided in Figure 3 having η∗=i,j,k, θij=0.8,θik=0.4,θjk=0.7;ψi,ij=0.7,ψj,ji=0.5,ψi,ik=0.3,ψk,ki=0.2,ψj,jk=0.3,ψk,kj=0.7. It is a subgraph of a FIG given in Example 1 (Figure 2) with CI1.1.Figure 3
Subgraph of the fuzzy incidence graph in Figure2.


## 3. Bounds for Connectivity Index of Fuzzy Incidence Graph

This section discusses some bounds for theCI of FIGs. Every FIG has a different CI. Therefore, all FIGs have different bounds for the CI. From all FIGs, the complete FIGs will have the highest CI. It is shown in the next theorem.Theorem 1.
Consider aFIG, G having η∗=n, then 0≤CIG≤CIG″, where G″ indicates a complete FIG.Proof.
AssumeG is a FIG. If θ∗=0, then CI of G=0. Let G″ be the complete FIG having η∗=n and η″a=ηa. Then, θa,b≤θ″a,b. Also, ICONNGa,b≤ICONNG″a,b. This implies 0≤CIG≤CIG″.Example 3.
AssumeG″ is a complete FIG given in Figure 4 having η∗=i,j,k, θij=0.8,θik=0.4,θjk=0.7,ψi,ij=0.8,ψj,ji=0.8,ψi,ik=0.4,ψk,ki=0.4,ψj,jk=0.7 and ψk,kj=0.7. We get CIG″=2.2.Figure 4
A complete fuzzy incidence graph.


## 4. Vertex-Deleted and Edge-Deleted Fuzzy Incidence Subgraphs with Connectivity Indices

This section talks about the deletion of some edge or vertex of anyFIG will become a cause of reducing a CI of FIG. An edge deleted and vertex deleted subgraph of a FIG will have small values of CI. The CI of FISs relies upon the nature of vertex or edge deleted.Example 4.
LetG=η,θ,ψ be the FIG given in Figure 5 with η∗=p,q,r,s,t, θpq=0.7,θpr=0.5,θqr=0.9,θrs=0.3,θrt=0.5,θst=0.6;ψp,pq=0.6,ψq,qp=0.7,ψp,pr=0.4,ψr,rp=0.2,ψq,qr=0.8,ψr,rq=0.6,ψr,rs=0.2,ψs,sr=0.3,ψr,rt=0.5,ψt,tr=0.4,ψs,st=0.6, and ψt,ts=0.4. After calculation, we get CIG=4.6, whereas CIG−qr=3.0 and CIG−rt=3.4. Here, we conclude that deletion of some of the incidence pair reduces CIG. This motivation leads us to the following result.Figure 5
Fuzzy incidence graph withCI4.6.Theorem 2.
LetG=η,θ,ψ be a FIG and G∗=η∗,θ∗,ψ∗ be the FIS of G by deleting an incidence pair a,ab∈ψ∗. Then, CIG∗<CIG iff a,ab is a FB.Proof.
Consider a paira,ab be a FB. Then, according to definition of FB, ICONNG−a,aba,b<ICONNGa,b, which shows that CIG∗<CIG. Conversely, assume that CIG∗<CIG. Now, consider three different cases:Case 1: consider aδ−pair, ψa,ab, and then ψa,ab<ICONNG−a,aba,b which implies ICONNG−a,aba,b<ICONNGa,b. This implies CIG∗<CIG.Case 2: consider aβ−strong incidence pair ψa,ab. Then, ψa,ab=ICONNG−a,aba,b which means that there is an another strongest path a,a,ab,ab,b,ab,b different from the edge ψa,ab. The IS does not affect when we delete ψa,ab. This means CIG∗=CIG.Case 3: consider anα−strong incidence pair ψa,ab. Then, ψa,ab>ICONNG−a,aba,b. This means an edge ab is the only strongest path whose strength is equal to ψa,ab. From this, it is obvious that CIG∗<CIG. As by definition α, strong arcs are FBs. This means if CIG∗<CIG, then ab is a FB. This shows that CIG∗<CIG iff uv is a FB.


## 5.ACI of FIG

We measure the average flow in the network to check how much flow is stable in the network. Therefore, in this section, we are going to introduce a new parameter namedACI of FIG. Assume the FIG given in Example 1.Example 5.
AssumeG is a FIG given in Example 1 (Figure 2) having η∗=i,j,k,l, θij=0.8,θik=0.4,θjk=0.7,θkl=0.9;ψi,ij=0.7,ψj,ji=0.5,ψi,ik=0.3,ψk,ki=0.2,ψj,jk=0.3,ψk,kj=0.7,ψk,kl=0.7 and ψl,lk=0.3 with CIG  = 2.0. G contains 4!/4−2!2!=6 pairs of nodes with ACIG=CIG/6=2/6=0.33.Definition 13.
Consider aFIG. The ACI of FIG is given by(2)ACIG=1n2∑a,b∈η∗ηaηbICONNGa,b.Definition 14.
Assume aFIG and z∈η∗. z will be FICRN of G if ACIG−z<ACIG. We call z a FICEN if ACIG−z>ACIG. z will be FICNN if ACIG−z=ACIG.Example 6.
LetG be a FIG given in Figure 6 with HTML translation failed, θij=0.3,θik=0.8,θjk=0.7,θjn=0.5,θkl=0.9,θlm=0.8;ψi,ij=0.3,ψj,ji=0.2,ψi,ik=0.4,ψk,ki=0.6,ψj,jk=0.6,ψk,kj=0.7,ψj,jn=0.5,ψn,nj=0.4,ψk,kl=0.8,ψl,lk=0.2,ψl,lm=0.3, and ψm,ml=0.7. ACIG=0.3,ACIG−i=0.29,ACIG−j=0.25,ACIG−k=0.11,ACIG−l=0.36,ACIG−m=0.34,ACIG−n=0.29. Therefore, i, j, k, and n are FICRNs; l and m are FICENs.Figure 6
Fuzzy incidence graph withFICRNs and FICENs.In the following proposition with the help ofCI, we classify these nodes:Proposition 3.
Consider aFIG. Let z∈η∗ having n=η∗≥3. Assume q=CIG/CIG−m. z is a FICEN iff q<n/n−2. z is a FICRN iff q>n/n−2. z is a FICNN iff q=n/n−2.Proof.
Letz be FICNN of FIG. Then, ACIG=ACIG−z, that is, CIG/n2=CIG−z/n−12 and CIG/CIG−z=n2/n−12, which implies CIG/CIG−z=n/n−2. By reversing the argument, the sufficient part can easily be proved. In similar manners, the other two cases can be solved.Definition 15.
LetG be a FIG. G will be FI connectivity enhancing graph if G contains minimum one FICEN. If G contains no FICEN and has minimum one FICRN, then we call it FI connectivity reducing graph. We call G a FI connectivity neutral graph if all nodes of G are neutral.


## 6. Wiener Index ofFIG

In this section, we establish the concept ofWI. WI is a topological index used in different fields like medicine, communication, and cryptology. A proper definition to calculate WI of FIG is given next.Definition 16.
LetG be a FIG. WI of G can be calculated as(3)WIG=∑a,b∈η∗ηaηbdsa,b,where dsa,b represents weights of those strong geodesics from a−b whose sum is minimum.Example 7.
ConsiderG be a FIG given in Figure 7 with η∗=i,j,k, θij=0.7,θik=0.8,θjk=0.7;ψi,ij=0.6,ψj,ji=0.6,ψi,ik=0.8,ψk,ki=0.8,ψj,jk=0.6,ψk,kj=0.6. Here, each incidence pair is a strong pair. Because i−j is a geodesic, it is a strongest path from i−j. Similarly, i−k and j−k are all strongest paths. Thus, WIG=4.Figure 7
Fuzzy incidence graph withWIG=4.Assume aFIG. Let H be the FIS of G. Then, it is not necessary that WIH≤WIG. It can be seen in the next exampleExample 8.
LetH=κ,ϕ,Ω is a FIS (see Figure 8) of G=η,θ,ψ (in Figure 7) such that ϕik=0 and ϕij=0.7,ϕjk=0.7,Ωi,ij=0.6,Ωj,ij=0.6,Ωj,jk=0.6,Ωk,jk=0.6. Geodesic from i to k is i,j,k. dsi,j=ψi,ij+ψj,ij=1.2 Similarly, dsi,k=2.4,dsj,k=1.2. Then, WIH=4.8 and WIG=4<WIH=4.8.Figure 8
Fuzzy incidence subgraph of Figure7.Link betweenWI and CI of a FIGInFIGs, it could be noted that CI will be less than WI.Example 9.
Consider aFIG given in Figure 9 with η∗=i,j,k,l, θij=0.8,θik=0.4,θjk=0.7,θkl=0.9;ψi,ij=0.5,ψj,ji=0.7,ψi,ik=0.3,ψk,ki=0.2,ψj,jk=0.3,ψk,kj=0.7,ψk,kl=0.7, and ψl,lk=0.3. This FIG contains each pair strong except ψi,ki=0.2 because ICONNG−i,ki=0.3. For i,k∈η∗×η∗∖ψi,ki. Now, CIG=0.5+0.3+0.3+0.3+0.3+0.3=2 and WIG=1.2+2.2+3.2+1+2+1=10.6 Thus, CIG<WIG.Figure 9
Fuzzy incidence graph withCI<WI.Theorem 3.
Assume aFIG having η∗≥3. Then, WIG>CIG.Proof.
Consider aFIG with η∗≥3. For every a,b∈η∗, the sum of membership values of every strong incidence pairs connecting a and b is dsa,b, whereas the minimum membership value of all strong incidence pairs is ICONNGa,b, which means ICOONGa,b<dsa,b. This implies ∑a,b∈η∗ηaηbICONNGa,b<∑a,b∈η∗ηaηbdsa,b. Hence, CIG<WIG.Theorem 4.
Assume a completeFIG, G with η∗=2, and a=b=1. Then, 2CIG=WIG.Proof.
ConsiderG be a complete FIG with η∗=2 and a=b=1. ∃ There exist a strong path P″ which is the strongest path in complete FIG, G. For any two nodes a,b∈η∗, the sum of membership values of incidence pair in the only strongest path P″ connecting a with b is dsa,b, whereas the minimum membership value of incidence pair of P is ICONNGa,b. This implies 2ICONNGa,b=dsa,b. Thus, 2∑a,b∈η∗ηaηbICONNGa,b=∑a,b∈η∗ηaηbdsa,b. Hence, 2CIG=WIG.Example 10.
LetG be the complete FIG, as shown in Figure 10. Here, u,v∈η∗ and θuv=0.3,ψu,uv=0.3,ψv,vu=0.3. Clearly, CIG=0.3 and WIG=0.6.Figure 10
Complete fuzzy incidence graph with2CIG=WIG.


## 7. Conclusion

Connectivity is an essential parameter attached to a network. The idea of connectivity is inseparable from the theory ofFIGs. In this paper, we have come up with different results about WI and CI of FIGs. Relevant examples related to WI and CI of FIGs are too obtained. In this article, CI, ACI, and WI of FIGs linked with networks are expressed. Nodes of FIGs are classified as FICRN,FICEN, and FICNN by using these incidences. Various types of FIGs are also obtained. A crucial relationship between CI and WI of FIG is derived too. Our objective is to enlarge our research work to soft FIGs, bipolar FIGs, threshold FIGs, competition FIGs, regular FIGs, and q-rung FIGs. More similar results and applications will be reported in upcoming papers.



---

*Source: 6682966-2021-02-04.xml*