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

$\backslash Omega\_\{i,j\}=0\backslash ,$.

For an undirected graph

\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 NXN matrix M:

$\backslash sum\_\{i,j\; \backslash in\; V\}(LML)\_\{i,j\}\backslash Omega\_\{i,j\}=-2tr(ML)\backslash ,$

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

$\backslash sum\_\{(i,j)\; \backslash in\; E\}\backslash Omega\_\{i,j\}=N-1$

where the $\backslash 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}=\begin{cases} \frac{\left | \{t:t \in T, e_{i,j} \subseteq T\} \right \vert}{\left | T \right \vert}, & (i,j) \in E\\ \frac{\left | T^\'-T \right \vert}{\left | T \right \vert}, &(i,j) \not \in E \end{cases}

where T^\' is the set of spanning trees for the graph $G^\backslash \text{'}=(V,\; E+e\_\{i,j\})$.

Classical mechanics

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

References

• Klein DJ, Randi M, "Resistance Distance", Journal of Mathematical Chemistry 12:81
• Klein DJ, "Resistance Distance Sum Rules"

This article is licensed under the GNU Free Documentation License. It uses material from Wikipedia