# 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 vi and vj is

${\displaystyle \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. Template:Clarify

## Properties of resistance distance

If i = j then

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

For an undirected graph

${\displaystyle \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 = (VE) and arbitrary N×N matrix M:

${\displaystyle \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;

${\displaystyle \sum _{(i,j)\in E}\Omega _{i,j}=N-1}$
${\displaystyle \sum _{i

where the ${\displaystyle \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 = (VE), the resistance distance between two vertices may by expressed as a function of the set of spanning trees, T, of G as follows:

${\displaystyle \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 ${\displaystyle T'}$ is the set of spanning trees for the graph ${\displaystyle G'=(V,E+e_{i,j})}$.

### As a squared Euclidean distance

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

${\displaystyle \Omega _{i,j}=\Gamma _{i,i}+\Gamma _{j,j}-\Gamma _{i,j}-\Gamma _{j,i}=K_{i}K_{i}^{T}+K_{j}K_{j}^{T}-K_{i}K_{j}^{T}-K_{j}K_{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 ${\displaystyle K}$.

### Connection with Fibonacci numbers

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

## References

• {{#invoke:Citation/CS1|citation

|CitationClass=journal }}

• {{#invoke:Citation/CS1|citation

|CitationClass=journal }}

• {{#invoke:Citation/CS1|citation

|CitationClass=journal }}

• {{#invoke:Citation/CS1|citation

|CitationClass=journal }}

• {{#invoke:Citation/CS1|citation

|CitationClass=journal }}

• {{#invoke:Citation/CS1|citation

|CitationClass=journal }}

• {{#invoke:Citation/CS1|citation

|CitationClass=journal }}

• {{#invoke:Citation/CS1|citation

|CitationClass=journal }}

• {{#invoke:Citation/CS1|citation

|CitationClass=journal }}

• {{#invoke:Citation/CS1|citation

|CitationClass=journal }}

• {{#invoke:Citation/CS1|citation

|CitationClass=journal }}

• {{#invoke:Citation/CS1|citation

|CitationClass=journal }}