# A Note on \"Wiener Index of a Fuzzy Graph and Application to Illegal Immigration Networks\"
## 3 A New Algorithm to Compute Wiener Index of a Fuzzy Graph  
Let \(G=(\sigma,\mu)\) be a fuzzy graph with \(|\sigma^{*}|=n\). The underlying graph of \(G=(\sigma,\mu)\) is denoted by \(G^{*}=(\sigma^{*},\mu^{*})\), where \(\sigma^{*}=\{v|\sigma(v)>0\}\) and \(\mu^{*}=\{uv|u(uv)>0\}\). [PERSON] et al. in [7] give an Algorithm 1 to compute Wiener index of a fuzzy graph as follows. ```
Step 1. Identify strong edges of \(G\) using the algorithm in [8]. Step 2. Let \(G^{\prime}=(\sigma^{\prime},\mu^{\prime})\) be the fuzzy subgraph of \(G\) obtained by deleting the \(\delta\)-edges of \(G\). Step 3. Use [PERSON]'s algorithm to identify geodesics between \(u\) and \(v\) in \(G^{{}^{\prime}*}\), for each \(u,v\in\sigma^{*}\). Let \(P^{1}\), \(P^{2}\), \(\cdots\), \(P^{k}\) be the geodesics connecting \(u\) and \(v\) in \(G^{{}^{\prime}*}\). Step 4. Calculate \(S_{p^{\prime}}\) for \(i=1,2,\cdots,k\), where \(S_{p^{i}}\) is the sum of membership values of edges of \(P^{i}\). Step 5. Let \(d_{S}(u,v)=\wedge\{S_{pi}|i=1,2,\cdots,k\}\). Step 6. Construct an \(n\times n\) matrix \(D\) corresponding to \(G=(\sigma,\mu)\) with the following properties. Each row and column corresponds to vertices in \(\sigma^{*}\). If row \(i\) corresponds to vertex \(u\) and column \(j\) corresponds to vertex \(v\), then \(d_{S}(u,v)\) is the entry corresponds to row \(i\) and column \(j\). Step 7. Calculate \(WI(G)=\sum_{u,v\in\sigma^{*}}\sigma(u)\sigma(v)d_{S}(u,v)\). ```  
**Algorithm 1**Computing Wiener index of a fuzzy graph [7]. The main drawback of the Algorithm 1 in [7] is as follows. [PERSON]'s algorithm is only used to identify the length of the shortest path between \(u\) and \(v\) in \(G^{{}^{\prime}*}\). However, it can not be used to identify the number \(k\) of the shortest path. For any big graph, the total number of the shortest path between \(u\) and \(v\) can be very high. In such case, it is difficult to perform Step 3 and Step 4. In order to give a simple algorithm to compute Wiener index of a fuzzy graph \(G=(\sigma,\mu)\), we define an operator on matrix as follows. Let \(G^{\prime}=(\sigma^{\prime},\mu^{\prime})\) be the fuzzy subgraph of \(G\) obtained by deleting the \(\delta\)-edges of \(G\). Let \(A^{1}=(a^{i}_{ij})_{n\times n}\) be the adjacent matrix of the fuzzy graph \(G^{\prime}\), where \(a^{1}_{ii}=0\) and \(a^{1}_{ij}=\mu^{\prime}(v_{i}v_{j})\) for \(i,j\in\{1,2,\cdots,n\}\). Let \(A^{k}=(a^{k}_{ij})_{n\times n}\) for \(i=2,3,\cdots,diam(G^{{}^{\prime}*})\), where \(diam(G^{{}^{\prime}*})\) denote the diameter of \(G^{{}^{\prime}*}\). Define \(A^{k+1}=A^{k}\) as follows:  
\[a^{k+1}_{ij}=\left\{ \begin{array}{ll}0,&\text{if $i=j$}\\ d^{k}_{ij},&\text{if $i\
eq j$ and $a^{k}_{ij}\
eq 0$}\\ \min_{1\leq t\leq n}\{a^{k}_{it}+a^{1}_{ij}|a^{k}_{it}\
eq 0,a^{1}_{ij}\
eq 0\},& \text{if $i\
eq j$ and $a^{k}_{ij}=0$}\end{array} \right.\]  
**Theorem 3**. : _Let \(G^{\prime}=(\sigma^{\prime},\mu^{\prime})\) be a fuzzy graph such that every edge is strong edge. If \(a^{k}_{ij}=0\) and \(a^{k+1}_{ij}\
eq 0\), then \(d(v_{i},v_{j})=k+1\) and \(d_{S}(v_{i},v_{j})=a^{k+1}_{ij}\), where \(d(v_{i},v_{j})\) is the distance between \(v_{i}\) and \(v_{j}\) in \(G^{{}^{\prime}*}\)._  
Proof. : We will prove it by induction on the number \(k\). Suppose \(k=1\). If \(a^{1}_{ij}\
eq 0\), then \(v_{i}v_{j}\in\mu^{{}^{\prime}}\) and \(a^{1}_{ij}=\mu^{\prime}(v_{i}v_{j})\). Since every edge in \(G^{\prime}\) is strong edge, then \(d(v_{i},v_{j})=1\) and \(d_{S}(v_{i},v_{j})=a^{1}_{ij}\). Suppose that \(a^{1}_{ij}=0\) and \(a^{2}_{ij}\
eq 0\). Then \(v_{i}v_{j}\
otin\mu^{{}^{\prime}}\). Since \(a^{2}_{ij}=\min_{1\leq t\leq n}\{a^{1}_{it}+a^{1}_{it}|a^{1}_{it}\
eq 0,a^{1}_{ ij}\
eq 0\}\), it follows that \(d(v_{i},v_{j})=2\) and \(d_{S}(v_{i},v_{j})=a^{2}_{ij}\). Assume that the theorem holds for \(k<l\). Suppose that \(a^{l}_{ij}=0\) and \(a^{l+1}_{ij}\
eq 0\). By definition, \(a^{l+1}_{ij}=\min_{1\leq t\leq n}\{a^{l}_{it}+a^{1}_{ij}|a^{l}_{it}\
eq 0,a^{1}_{ ij}\
eq 0\}\).