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$

:

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:

:

where "T"^' is the set of spanning trees for the graph $G^\text{'}=(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"]