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.
On a graph G, the resistance distance Ωi,j between two vertices vi and vj is[1] 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.
For an undirected graph For any N-vertex simple connected graph G = (V, E) and arbitrary N×N matrix M: From this generalized sum rule a number of relationships can be derived depending on the choice of M. Two of note are; where the λk 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 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: where T' is the set of spanning trees for the graph G' = (V, E + ei,j).
, the resistance distance between a pair of nodes
The resistance distance between vertices
The commute time is the expected number of steps in a random walk that starts at
edges, the resistance distance and commute time are related as
[2] Since the Laplacian L is symmetric and positive semi-definite, so is thus its pseudo-inverse Γ is also symmetric and positive semi-definite.
and we can write: showing that the square root of the resistance distance corresponds to the Euclidean distance in the space spanned by K. 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 where Fj is the j-th Fibonacci number, for j ≥ 0.