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 resistance of one ohm. 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^[1]

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

where

\Gamma =\left(L+{\frac {1}{|V|}}\Phi \right)^{+},

with $+$ denotes the Moore–Penrose inverse, $L$ the Laplacian matrix of $G$ , $| V |$ is the number of vertices in $G$ , and $Φ$ is the $| V | \times | V |$ matrix containing all 1s.

Properties of resistance distance

If $i = j$ then $Ω 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 \times 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;

{\begin{aligned}\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}\end{aligned}}

where the $λ k$ 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 $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:

\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)$ . 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}=2m\Omega _{u,v}$ .^[2]

As a squared Euclidean distance

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

\left(L+{\frac {1}{|V|}}\Phi \right),

thus its pseudo-inverse $Γ$ is also symmetric and positive semi-definite. Thus, there is a $K$ such that $\Gamma =KK^{\textsf {T}}$ and we can write:

\Omega _{i,j}=\Gamma _{i,i}+\Gamma _{j,j}-\Gamma _{i,j}-\Gamma _{j,i}=K_{i}K_{i}^{\textsf {T}}+K_{j}K_{j}^{\textsf {T}}-K_{i}K_{j}^{\textsf {T}}-K_{j}K_{i}^{\textsf {T}}=\left(K_{i}-K_{j}\right)^{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, \dots, n$ , and there is an edge between vertex $i$ and $i + 1$ for all $i = 1, 2, 3, \dots, n - 1$ .

The resistance distance between vertex $n + 1$ and vertex $i \in {1, 2, 3, \dots, 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$ .^[3]

References

^ "Resistance Distance".
^ Chandra, Ashok K and Raghavan, Prabhakar and Ruzzo, Walter L and Smolensky, Roman (1989). "The electrical resistance of a graph captures its commute and cover times". Proceedings of the twenty-first annual ACM symposium on Theory of computing - STOC '89. pp. 574–685. doi:10.1145/73007.73062. ISBN 0897913078.{{cite book}}: CS1 maint: multiple names: authors list (link)
^ Bapat, R. B.; Gupta, Somit (2010). "Resistance distance in wheels and fans" (PDF). Indian Journal of Pure and Applied Mathematics. 41 (1): 1–13. doi:10.1007/s13226-010-0004-2. MR 2650096.

Klein, D. J.; Randic, M. J. (1993). "Resistance Distance". J. Math. Chem. 12: 81–95. doi:10.1007/BF01164627. S2CID 16382100.
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" (PDF). Croatica Chem. Acta. 75 (2): 633–649. Archived from the original (PDF) on 2012-03-26.
Bapat, Ravindra B.; Gutman, Ivan; Xiao, Wenjun (2003). "A simple method for computing resistance distance". Z. Naturforsch. 58a (9–10): 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. S2CID 120309331.
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. Bibcode:2008IJQC..108.1200B. doi:10.1002/qua.21588.
Zhou, Bo; Trinajstic, Nenad (2009). "The Kirchhoff index and the matching number". Int. J. Quantum Chem. 109 (13): 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. hdl:10338.dmlcz/140814. S2CID 119389248.
Zhou, Bo (2011). "On sum of powers of Laplacian eigenvalues and Laplacian Estrada Index of graphs". Match Commun. Math. Comput. Chem. 62: 611–619. arXiv:1102.1144.

Zhang, Heping; Yang, Yujun (2007). "Resistance distance and Kirchhoff index in circulant graphs". Int. J. Quantum Chem. 107 (2): 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 (44): 445203. Bibcode:2008JPhA...41R5203Y. doi:10.1088/1751-8113/41/44/445203. S2CID 122226781.

[1] "Resistance Distance".

[2] Chandra, Ashok K and Raghavan, Prabhakar and Ruzzo, Walter L and Smolensky, Roman (1989). "The electrical resistance of a graph captures its commute and cover times". Proceedings of the twenty-first annual ACM symposium on Theory of computing - STOC '89. pp. 574–685. doi:10.1145/73007.73062. ISBN 0897913078.{{cite book}}: CS1 maint: multiple names: authors list (link)

[3] Bapat, R. B.; Gupta, Somit (2010). "Resistance distance in wheels and fans" (PDF). Indian Journal of Pure and Applied Mathematics. 41 (1): 1–13. doi:10.1007/s13226-010-0004-2. MR 2650096.

[1]

[2]

[3]