Resistance distance

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

Definition

On a graph G, the resistance distance Ω_i,j between two vertices v_i and v_j is

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

where $\mathrm{\Gamma }={(L+\frac{1}{|V|}\mathrm{\Phi })}^{+}$, with ${+}^{}$ denoting the Moore–Penrose inverse, $L$ the Laplacian matrix of G, $|V|$ is the number of vertices in G, and $\mathrm{\Phi }$ is the $|V|\times |V|$ matrix containing all 1s.

Properties of resistance distance

If i = j then

${\mathrm{\Omega }}_{i,j}=0.$

For an undirected graph

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

General sum rule

For any N-vertex simple connected graph G = (V, E) and arbitrary N×N matrix M:

$\sum _{i,j\in V}(LML{)}_{i,j}{\mathrm{\Omega }}_{i,j}=-2\mathrm{tr}(ML)$

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

$\begin{array}{rl}\sum _{(i,j)\in E}{\mathrm{\Omega }}_{i,j}& =N-1\\ \sum _{i<j\in V}{\mathrm{\Omega }}_{i,j}& =N\sum _{k=1}^{N-1}{\lambda }_k^{-1}\end{array}$

where the ${\lambda }_k$ are the non-zero eigenvalues of the Laplacian matrix. This unordered sum Σ_i<jΩ_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 G = (V, E), the resistance distance between two vertices may be expressed as a function of the set of spanning trees, T, of G as follows:

${\mathrm{\Omega }}_{i,j}=\{\begin{array}{ll}\frac{|\{t:t\in T,e_{i,j}\in t\}|}{\left|T\right|},& (i,j)\in E\\ \frac{|T^{\prime }-T|}{\left|T\right|},& (i,j)\in ̸E\end{array}$

where $T^{\prime }$ is the set of spanning trees for the graph $G^{\prime }=(V,E+e_{i,j})$.

As a squared Euclidean distance

Since the Laplacian $L$ is symmetric and positive semi-definite, so is $(L+\frac{1}{|V|}\mathrm{\Phi })$, thus its pseudo-inverse $\mathrm{\Gamma }$ is also symmetric and positive semi-definite. Thus, there is a $K$ such that $\mathrm{\Gamma }=K{K}^{\text{T}}$ and we can write:

${\mathrm{\Omega }}_{i,j}={\mathrm{\Gamma }}_{i,i}+{\mathrm{\Gamma }}_{j,j}-{\mathrm{\Gamma }}_{i,j}-{\mathrm{\Gamma }}_{j,i}=K_i{K}_i^{\text{T}}+K_j{K}_j^{\text{T}}-K_i{K}_j^{\text{T}}-K_j{K}_i^{\text{T}}={(K_i-K_j)}^2$

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

Connection with Fibonacci numbers

A fan graph is a graph on $n+1$ vertices where there is an edge between vertex $i$ and $n+1$ for all $i=1,2,3,...n,$ and there is an edge between vertex $i$ and $i+1$ for all $i=1,2,3,...,n-1.$

The resistance distance between vertex $n+1$ and vertex $i\in \{1,2,3,...,n\}$ is $\frac{F_{2(n-i)+1}{F}_{2i-1}}{F_{2n}}$ where $F_j$ is the $j$-th Fibonacci number, for $j\ge 0$.

See also

• Conductance (graph)

References

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

• Zhang, Heping; Yang, Yujun (2007). "Resistance distance and Kirchhoff index in circulant graphs". Int. J. Quantum Chem. 107 (2): 330–339. doi:10.1002/qua.21068. Bibcode: 2007IJQC..107..330Z. 

• Yang, Yujun; Zhang, Heping (2008). "Some rules on resistance distance with applications". J. Phys. A: Math. Theor. 41 (44): 445203. doi:10.1088/1751-8113/41/44/445203. Bibcode: 2008JPhA...41R5203Y.