Resistance distance

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 defined as

:$$Omega_{i,j}:=Gamma_{i,i}+Gamma_{j,j}-Gamma_{i,j}-Gamma_{j,i},

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

Properties of resistance distance

If "i=j" then

:$$Omega_{i,j}=0,.

For an undirected graph

:$$Omega_{i,j}=Omega_{j,i}=Gamma_{i,i}+Gamma_{j,j}-2Gamma_{i,j},

General sum rule

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

:$$sum_{i,j in V}(LML)_{i,j}Omega_{i,j}=-2tr(ML),

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

:$$sum_{(i,j) in E}Omega_{i,j}=N-1

:$$sum_{i

where the $$lambda_{k} are the non-zero eigenvalues of the Laplacian matrix.

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:

:$$Omega_{i,j}=egin{cases}frac{left | {t:t in T, e_{i,j} subseteq T} ight vert}{left | T ight vert}, & (i,j) in E\ frac{left | T^'-T ight vert}{left | T ight vert}, &(i,j) ot in E end{cases}

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, it's pseudoinverse $$Gamma is also symmetric and positive semi-definite. Thus, there is a $$K such that $$Gamma = K K^T and we can write:

:$$Omega_{i,j} = Gamma_{i,i}+Gamma_{j,j}-Gamma_{i,j}-Gamma_{j,i} = K_iK_i^T + K_jK_j^T - K_iK_j^T - K_jK_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.

Classical mechanics

In classical mechanics, resistance distance is defined as the distance from the resistance (on a lever) to the fulcrum.

References

* [http://www.springerlink.com/content/n66x902225127243/ Klein DJ, Randi M, "Resistance Distance", Journal of Mathematical Chemistry 12:81 ]
* [http://jagor.srce.hr/ccacaa/CCA-PDF/cca2002/v75-n2/CCA_75_2002_633_649_KLEIN.pdf Klein DJ, "Resistance Distance Sum Rules"]