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. It is a metric on graphs.
Definition On a graph G, the resistance distance Ωi,j between two vertices vi and vj is
Ω i , j := Γ i , i + Γ j , j − Γ i , j − Γ j , i , {\displaystyle \Omega _{i,j}:=\Gamma _{i,i}+\Gamma _{j,j}-\Gamma _{i,j}-\Gamma _{j,i},}
where Γ = ( L + 1 | V | Φ ) + , {\displaystyle \Gamma =\left(L+{\frac {1}{|V|}}\Phi \right)^{+},}
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.
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 {\displaystyle \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 = (V, E) and arbitrary N×N matrix M:
∑ i , j ∈ V ( L M L ) i , j Ω i , j = − 2 tr ( M L ) {\displaystyle \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;
∑ ( i , j ) ∈ E Ω i , j = N − 1 ∑ i < j ∈ V Ω i , j = N ∑ k = 1 N − 1 λ k − 1 {\displaystyle {\begin{aligned}\sum _{(i,j)\in E}\Omega _{i,j}&=N-1\\\sum _{i<j\in V}\Omega _{i,j}&=N\sum _{k=1}^{N-1}\lambda _{k}^{-1}\end{aligned}}}
where the λk are the non-zero eigenvalues of the Laplacian matrix. This unordered sum
∑ i < j Ω i , j {\displaystyle \sum _{i<j}\Omega _{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 be expressed as a function of the set of spanning trees, T, of G as follows:
… excerpt ends here. Continue reading the full article.
