# 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
For any \(a^{l}_{it}\
eq 0\) and \(a^{1}_{ij}\
eq 0\), if there exists \(l^{\prime}<l\) such that \(a^{l^{\prime}}_{it}\
eq 0\), then \(a^{l^{\prime}+1}_{ij}\
eq 0\). Since \(l^{\prime}+1\leq l\), it follows that \(a^{l}_{ij}\
eq 0\), which is a contradiction. Hence for any \(l^{\prime}<l\), \(a^{l^{\prime}}_{it}=0\). That is \(a^{l-1}_{it}=0\) and \(a^{l}_{it}\
eq 0\). By inductive hypotheses on \(k\), it follows that \(d(v_{i},v_{t})=l\) and \(d_{S}(v_{i},v_{t})=a^{l}_{it}\). Since\(a_{ij}^{l+1}=\min_{1\leq t\leq n}\{a_{it}^{l}+a_{ij}^{1}|a_{it}^{l}\
eq 0,a_{ij}^{1} \
eq 0\}\), there exists \(t\) such that \(a_{ij}^{l+1}=a_{it}^{l}+a_{ij}^{1}\), where \(a_{it}^{l}\
eq 0\) and \(a_{ij}^{1}\
eq 0\). Since \(d(v_{i},v_{t})=l\) and \(d_{S}(v_{i},v_{t})=a_{it}^{l}\), it follows that \(d(v_{i},v_{j})=l+1\) and \(d_{S}(v_{i},v_{j})=a_{ij}^{l+1}\). **Corollary 1**. : _Let \(G^{\prime}=(\sigma^{\prime},\mu^{\prime})\) be a fuzzy graph such that every edge is strong edge. Let \(diam(G^{\prime*})\) be the diameter of \(G^{{}^{\prime}*}\). Then for any two vertices \(v_{i},v_{j}\in\sigma^{\prime}\), \(d_{S}(v_{i},v_{j})=a_{ij}^{diam(G^{{}^{\prime}*})}\), where \(i,j\in\{1,2,\cdots,n\}\)._ \begin{tabular}{c} \hline \hline 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. Calculate \(A^{1},A^{2},\cdots,A^{diam(G^{\prime*})}\), where \(d_{S}(v_{i},v_{j})=a_{ij}^{diam(G^{{}^{\prime}*})}\) for \\ \(1\leq i<j\leq n\). \\ Step 4. Calculate \(WI(G)=\sum_{u,v\in\sigma^{\prime}}\sigma(u)\sigma(v)d_{S}(u,v)\). \\ \hline \end{tabular}   
Obviously, it is a polynomial-time algorithm. The correctness of the Algorithm 2 follows from Theorem 3 and Corollary 1. So we have the following:  
**Theorem 4**. : _Let \(G=(\sigma,\mu)\) be a fuzzy graph. Let \(A^{1},A^{2},\cdots,A^{diam(G^{\prime*})}\) be defined as in the Algorithm 2. Then \(WI(G)=\sum_{1\leq i<j\leq n}\sigma(v_{i})\sigma(v_{j})a_{ij}^{diam(G^{{}^{ \prime}*})}\)._  
Proof. : By Theorem 3, let \(G^{\prime}=(\sigma^{\prime},\mu^{\prime})\) be a fuzzy graph such that every edge is strong edge. If \(a_{ij}^{k}=0\) and \(a_{ij}^{k+1}\
eq 0\), then \(d(v_{i},v_{j})=k+1\) and \(d_{S}(v_{i},v_{j})=a_{ij}^{k+1}\). By the definition on the new operator on matrix, for any two vertices \(v_{i},v_{j}\in\sigma^{\prime}\), \(d_{S}(v_{i},v_{j})=a_{ij}^{diam(G^{\prime*})}\), where \(i,j\in\{1,2,\cdots,n\}\). So, \(WI(G)=\sum_{1\leq i<j\leq n}\sigma(v_{i})\sigma(v_{j})a_{ij}^{diam(G^{{}^{ \prime}*})}\). **Example 3**. : _Let \(G=(\sigma,\mu)\) be the fuzzy graph shown in Figure 4 with vertex set \(\{a,b,c,d,e\}\) and \(\sigma(v)=1\) for any \(v\in\sigma^{*}\), \(\mu(ab)=0.2\), \(\mu(ac)=0.2\), \(\mu(bc)=0.3\), \(\mu(cd)=0.4\), \(\mu(de)=0.5\). Then each edge of the graph \(G\) is strong._ \begin{tabular}{c} \hline \hline \(A^{1}\) & a & b & c & d & e \\ \hline a & 0 & 0.2 & 0.2 & 0 & 0 \\ b & 0.2 & 0 & 0.3 & 0 & 0 \\ c & 0.2 & 0.3 & 0 & 0.4 & 0 \\ d & 0 & 0 & 0.4 & 0 & 0.5 \\ e & 0 & 0 & 0 & 0.5 & 0 \\ \hline \hline \end{tabular}   
By using Algorithm 2 and \(diam(G^{\prime*})=3\), we can compute \(A^{1}\), \(A^{2}\), and \(A^{3}\) as follows: \begin{tabular}{c} \hline \hline \(A^{2}\) & a & b & c & d & e \\ \hline a & 0 & 0.2 & 0.2 & 0.6 & 0 \\ b & 0.2 & 0 & 0.3 & 0.7 & 0 \\ c & 0.2 & 0.3 & 0 & 0.4 & 0.9 \\ d & 0.6 & 0.7 & 0.4 & 0 & 0.5 \\ e & 0 & 0 & 0.9 & 0.5 & 0 \\ \hline \hline \end{tabular}   
Figure 4: Fuzzy graph \(G\) with \(diam(G^{{}^{\prime}*})=3\). As membership values of all vertices are one, the sum of all upper triangular entries of \(A^{3}\) will be the \(WI\) of \(G\). Hence \(WI(G)=6.1\).