 #jsDisabledContent { display:none; } My Account |  Register |  Help Flag as Inappropriate This article will be permanently flagged as inappropriate and made unaccessible to everyone. Are you certain this article is inappropriate?          Excessive Violence          Sexual Content          Political / Social Email this Article Email Address:

# Resistance distance

Article Id: WHEBN0000695230
Reproduction Date:

 Title: Resistance distance Author: World Heritage Encyclopedia Language: English Subject: Collection: Graph Theory Publisher: World Heritage Encyclopedia Publication Date:

### 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.

## Contents

• Definition 1
• Properties of resistance distance 2
• General sum rule 2.1
• Relationship to the number of spanning trees of a graph 2.2
• As a squared Euclidean distance 2.3
• Connection with Fibonacci numbers 2.4
• References 4

## Definition

On a graph G, the resistance distance Ωi,j between two vertices vi and vj 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 = (VE) 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

where the \lambda_{k} are the non-zero eigenvalues of the Laplacian matrix. This unordered sum ΣiΩ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:

\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.