Resistance distance explained

In graph theory, the resistance distance between two vertices of a simple, connected graph,, is equal to the resistance between two equivalent points on an electrical network, constructed so as to correspond to, with each edge being replaced by a resistance of one ohm. It is a metric on graphs.

Definition

On a graph, the resistance distance between two vertices and is^[1]

\Omega _{i,j} : = \Gamma _{i,i} + \Gamma _{j,j} - \Gamma _{i,j} - \Gamma _{j,i} ,

where

\Gamma = \left(L + (1)/(|V|) \Phi\right) ^{+,} with denotes the Moore–Penrose inverse, the Laplacian matrix of, is the number of vertices in, and is the matrix containing all 1s.

Properties of resistance distance

If then . For an undirected graph

\Omega _{i,j} = \Omega _{j,i} = \Gamma _{i,i} + \Gamma _{j,j} -2 \Gamma _{i,j}

General sum rule

For any -vertex simple connected graph and arbitrary matrix :

\sum _{i,j} (LML) _{i,j} \Omega _{i,j} = -2 \operatorname{tr}(ML)

From this generalized sum rule a number of relationships can be derived depending on the choice of . Two of note are;

\begin{align} \sum _{(i,j)} \Omega _{i,j} & = N - 1 \\ \sum _{i<j} \Omega _{i,j} & = N\sum ^{N -1} _{k =1} λ ^{-1} _{k} \end{align}

where the are the non-zero eigenvalues of the Laplacian matrix. This unordered sum

\sum _{i<j} \Omega _{i,j} is called the Kirchhoff index of the graph.

Relationship to the number of spanning trees of a graph

For a simple connected graph, the resistance distance between two vertices may be expressed as a function of the set of spanning trees,, of as follows:

\Omega _{i,j} = \begin{cases} (\left | \{t:t \in T, e _{i,j} \in t\)/(\right) \vert}{\left | T \right \vert}, & (i,j) \in E\ (\left | T' - T \right \vert)/(\left | T \right \vert) , &(i,j) \not \in E \end{cases}

where is the set of spanning trees for the graph . In other words, for an edge

(i,j)\in E , the resistance distance between a pair of nodes i and j is the probability that the edge (i,j) is in a random spanning tree of G .

Relationship to random walks

The resistance distance between vertices

u and u is proportional to the commute time C _{u,v} of a random walk between u and v . The commute time is the expected number of steps in a random walk that starts at u , visits v , and returns to u . For a graph with m edges, the resistance distance and commute time are related as C _{u,v} =2 m\Omega _{u,v} .^[2]

As a squared Euclidean distance

Since the Laplacian is symmetric and positive semi-definite, so is

\left(L + (1)/(|V|) \Phi\right), thus its pseudo-inverse is also symmetric and positive semi-definite. Thus, there is a such that \Gamma = KK ^{sf{T}} and we can write:\Omega _{i,j} = \Gamma _{i,i} + \Gamma _{j,j} - \Gamma _{i,j} - \Gamma _{j,i} = K _{iK} ^{sf{T} +} ^{i} K _{j} K ^{sf{T} -} _{j} K _{i} K ^{sf{T} -} _{j} K _{j} K ^{sf{T} =} _{i} \left(K _{i} - K ^{2} _{j\right)}

showing that the square root of the resistance distance corresponds to the Euclidean distance in the space spanned by .

Connection with Fibonacci numbers

A fan graph is a graph on vertices where there is an edge between vertex and for all, and there is an edge between vertex and for all .

The resistance distance between vertex and vertex is

(F _{2(n-i)+1} F _{2i-1})/(F _{2n}) where is the -th Fibonacci number, for .^[3]

See also

• Conductance (graph)

References

• D. J.. Klein. M. J.. Randic. J. Math. Chem.. 10.1007/BF01164627. Resistance Distance. 12. 81–95. 1993. 16382100.
• Ivan. Gutman. Bojan. Mohar. The quasi-Wiener and the Kirchhoff indices coincide. 1996. J. Chem. Inf. Comput. Sci.. 36. 5. 982–985. 10.1021/ci960007t.
• Closed-form formulas for the Kirchhoff index. Jose Luis. Palacios. Int. J. Quantum Chem.. 2001. 81. 2. 135–140. 10.1002/1097-461X(2001)81:2<135::AID-QUA4>3.0.CO;2-G.
• D.. Babic. D. J.. Klein. I.. Lukovits. S.. Nikolic. N.. Trinajstic. Resistance-distance matrix: a computational algorithm and its application. Int. J. Quantum Chem.. 2002. 10.1002/qua.10057. 90. 1. 166–167.
• Resistance Distance Sum Rules . Croatica Chem. Acta . Klein . D. J. . 2002 . 75 . 2 . 633–649 . dead . https://web.archive.org/web/20120326104653/http://www.stkpula.hr/ccacaa/CCA-PDF/cca2002/v75-n2/CCA_75_2002_633_649_KLEIN.pdf . 2012-03-26.
• Ravindra B.. Bapat. Ivan. Gutman. Wenjun. Xiao. A simple method for computing resistance distance. Z. Naturforsch.. 2003. 58a. 9–10. 494–498. 2003ZNatA..58..494B . 10.1515/zna-2003-9-1003 . free.
• Jose Luis. Placios. Foster's formulas via probability and the Kirchhoff index. Method. Comput. Appl. Probab.. 2004. 6. 4. 381–387. 10.1023/B:MCAP.0000045086.76839.54. 120309331.
• Enrique. Bendito. Angeles. Carmona. Andres M.. Encinas. Jose M.. Gesto. A formula for the Kirchhoff index. Int. J. Quantum Chem.. 2008. 10.1002/qua.21588. 1200–1206. 108. 6. 2008IJQC..108.1200B .
• Int. J. Quantum Chem.. Bo. Zhou. The Kirchhoff index and the matching number. Nenad. Trinajstic. 109. 13. 2009. 2978–2981. 10.1002/qua.21915. 2009IJQC..109.2978Z .
• Bo. Zhou. Nenad. Trinajstic. On resistance-distance and the Kirchhoff index. J. Math. Chem.. 2009. 46. 283–289. 10.1007/s10910-008-9459-3. 10338.dmlcz/140814. 119389248. free.
• Bo. Zhou. On sum of powers of Laplacian eigenvalues and Laplacian Estrada Index of graphs. Match Commun. Math. Comput. Chem. 62. 611–619. 1102.1144. 2011.
• Heping. Zhang. Yujun. Yang. Resistance distance and Kirchhoff index in circulant graphs. Int. J. Quantum Chem.. 2007. 107. 2. 330–339. 10.1002/qua.21068. 2007IJQC..107..330Z .
• Yujun. Yang. Heping. Zhang. Some rules on resistance distance with applications. J. Phys. A: Math. Theor.. 2008. 41. 44. 445203. 10.1088/1751-8113/41/44/445203. 2008JPhA...41R5203Y . 122226781.

Notes and References

1. Web site: Resistance Distance.
2. Book: Chandra, Ashok K and Raghavan, Prabhakar and Ruzzo, Walter L and Smolensky, Roman . Proceedings of the twenty-first annual ACM symposium on Theory of computing - STOC '89 . The electrical resistance of a graph captures its commute and cover times . 1989 . 21 . 574–685 . 10.1145/73007.73062 . 0897913078 . https://dl.acm.org/doi/abs/10.1145/73007.73062.
3. Bapat . R. B. . Gupta . Somit . 10.1007/s13226-010-0004-2 . 1 . Indian Journal of Pure and Applied Mathematics . 2650096 . 1–13 . Resistance distance in wheels and fans . 41 . 2010.