# 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
    $\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| × |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×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}$.

### 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, …, 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 ∈ {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 ≥ 0.