Resistance distance

In graph theory, the resistance distance between two vertices of a simple, connected graph,, is equal to the resistance between two equivalent points on an electrical network, constructed so as to correspond to, with each edge being replaced by a resistance of one ohm. It is a metric on graphs.

Definition

On a graph, the resistance distance between two vertices and is
with denotes the Moore–Penrose inverse, the Laplacian matrix of, is the number of vertices in, and is the matrix containing all 1s.

Properties of resistance distance

If then. For an undirected graph

General sum rule

For any -vertex simple connected graph and arbitrary matrix :
From this generalized sum rule a number of relationships can be derived depending on the choice of. Two of note are;
where the are the non-zero eigenvalues of the Laplacian matrix. This unordered sum
is called the Kirchhoff index of the graph.

Relationship to the number of spanning trees of a graph

For a simple connected graph, the resistance distance between two vertices may be expressed as a function of the set of spanning trees,, of as follows:
where is the set of spanning trees for the graph. In other words, for an edge, the resistance distance between a pair of nodes and is the probability that the edge is in a random spanning tree of.

Relationship to random walks

The resistance distance between vertices and is proportional to the commute time of a random walk between and. The commute time is the expected number of steps in a random walk that starts at, visits, and returns to. For a graph with edges, the resistance distance and commute time are related as.
Resistance distance is also related to the escape probability between two vertices. The escape probability between and is the probability that a random walk starting at visits before returning to. The escape probability equals
where is the degree of. Unlike the commute time, the escape probability is not symmetric in general, i.e.,.

As a squared Euclidean distance

Since the Laplacian is symmetric and positive semi-definite, so is
thus its pseudo-inverse is also symmetric and positive semi-definite. Thus, there is a such that and we can write:
showing that the square root of the resistance distance corresponds to the Euclidean distance in the space spanned by.

Connection with Fibonacci numbers

A fan graph is a graph on vertices where there is an edge between vertex and for all, and there is an edge between vertex and for all.
The resistance distance between vertex and vertex is
where is the -th Fibonacci number, for.