Resistance distance - Alchetron, The Free Social Encyclopedia

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 v_i and v_j is

Ω i , j := Γ i , i + Γ j , j − Γ i , j − Γ j , i

where Γ is the Moore–Penrose inverse of the Laplacian matrix of G.

Properties of resistance distance

If i = j then

Ω i , j = 0.

For an undirected graph

Ω i , j = Ω j , i = Γ i , i + Γ j , j − 2 Γ i , j

General sum rule

For any N-vertex simple connected graph G = (V, E) and arbitrary N×N matrix M:

∑ i , j ∈ V ( L M L ) i , j Ω i , j = − 2 tr ⁡ ( M L )

From this generalized sum rule a number of relationships can be derived depending on the choice of M. Two of note are;

∑ ( i , j ) ∈ E Ω i , j = N − 1 ∑ i < j ∈ V Ω i , j = N ∑ k = 1 N − 1 λ k − 1

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

Ω i , j = { | { t : t ∈ T , e i , j ∈ t } | | T | , ( i , j ) ∈ E | T ′ − T | | T | , ( i , j ) ∉ E

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 Γ is also symmetric and positive semi-definite. Thus, there is a K such that Γ = K K T and we can write:

Ω i , j = Γ i , i + Γ j , j − Γ i , j − Γ 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 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 ∈ { 1 , 2 , 3 , . . . , n } is F 2 ( n − i ) + 1 F 2 i − 1 F 2 n where F j is the j -th Fibonacci number, for j ≥ 0 .

References

Resistance distance Wikipedia

(Text) CC BY-SA

Contents