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.
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.
If then . For an undirected graph
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.
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 .
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., .
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 .
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 .