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

$\Omega_{i,j}:=\Gamma_{i,i}+\Gamma_{j,j}-\Gamma_{i,j}-\Gamma_{j,i}\,$

where Γ is the Moore–Penrose inverse of the Laplacian matrix of G.

Properties of resistance distance

If i = j then

$\Omega_{i,j}=0.\,$

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 N-vertex simple connected graph G = (V, E) and arbitrary N×N matrix M:

$\sum_{i,j \in V}(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 M. Two of note are;

$\sum_{(i,j) \in E}\Omega_{i,j}=N-1$

$\sum_{i<j \in V}\Omega_{i,j}=N\sum_{k=1}^{N-1} \lambda_{k}^{-1}$

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 by expressed as a function of the set of spanning trees, T, of G as follows:

$\Omega_{i,j}=\begin{cases} \frac{\left | \{t:t \in T, e_{i,j} \in t\} \right \vert}{\left | T \right \vert}, & (i,j) \in E\\ \frac{\left | T'-T \right \vert}{\left | T \right \vert}, &(i,j) \not \in E \end{cases}$

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

As a squared Euclidean distance

Since the Laplacian $L$ is symmetric and positive semi-definite, its pseudoinverse $\Gamma$ is also symmetric and positive semi-definite. Thus, there is a $K$ such that $\Gamma = K K^T$ and we can write:

$\Omega_{i,j} = \Gamma_{i,i}+\Gamma_{j,j}-\Gamma_{i,j}-\Gamma_{j,i} = K_iK_i^T + K_jK_j^T - K_iK_j^T - K_jK_i^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 \geq 0$.^[1][2]

See also

• Conductance (graph)

References

1. http://link.springer.com/article/10.1007/s13226-010-0004-2
2. http://www.isid.ac.in/~rbb/somitnew.pdf

• Klein, D. J.; Randic, M. J. (1993). "Resistance Distance". J. Math. Chem. 12: 81. doi:10.1007/BF01164627.
• Gutman, Ivan; Mohar, Bojan (1996). "The quasi-Wiener and the Kirchhoff indices coincide". J. Chem. Inf. Comput. Sci. 36: 982–985. doi:10.1021/ci960007t.
• Palacios, Jose Luis (2001). "Closed-form formulas for the Kirchhoff index". Int. J. Quant. Chem. 81: 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. Quant. Chem. 90 (1): 166–167. doi:10.1002/qua.10057.
• Klein, D. J. (2002). "Resistance Distance Sum Rules" (PDF). Croatica Chem. Acta 75 (2): 633–649.
• Bapat, Ravindra B.; Gutman, Ivan; Xiao, Wenjun (2003). "A simple method for computing resistance distance". Z. Naturforsch. 58a: 494–498. Bibcode:2003ZNatA..58..494B. doi:10.1515/zna-2003-9-1003.
• 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 Kirhhoff index". Int. J. Quant. Chem. 108 (6): 1200–1206. Bibcode:2008IJQC..108.1200B. doi:10.1002/qua.21588.
• Zhou, Bo; Trinajstic, Nenad (2009). "The Kirchhoff index and the matching number". Int. J. Quant. Chem. 109: 2978–2981. Bibcode:2009IJQC..109.2978Z. doi:10.1002/qua.21915.
• 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. "On sum of powers of Laplacian eigenvalues and Laplacian Estrada Index of graphs". arXiv:1102.1144.

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

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