Resistance distance

From HandWiki

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 vi and vj is[1]

[math]\displaystyle{ \Omega_{i,j}:=\Gamma_{i,i}+\Gamma_{j,j}-\Gamma_{i,j}-\Gamma_{j,i} }[/math]

where [math]\displaystyle{ \Gamma = \left(L + \frac{1}{|V|}\Phi\right)^+ }[/math], with [math]\displaystyle{ ^+ }[/math] denoting the Moore–Penrose inverse, [math]\displaystyle{ L }[/math] the Laplacian matrix of G, [math]\displaystyle{ |V| }[/math] is the number of vertices in G, and [math]\displaystyle{ \Phi }[/math] is the [math]\displaystyle{ |V|\times|V| }[/math] matrix containing all 1s.

Properties of resistance distance

If i = j then

[math]\displaystyle{ \Omega_{i,j}=0. }[/math]

For an undirected graph

[math]\displaystyle{ \Omega_{i,j}=\Omega_{j,i}=\Gamma_{i,i}+\Gamma_{j,j}-2\Gamma_{i,j} }[/math]

General sum rule

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

[math]\displaystyle{ \sum_{i,j \in V}(LML)_{i,j}\Omega_{i,j} = -2\operatorname{tr}(ML) }[/math]

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

[math]\displaystyle{ \begin{align} \sum_{(i,j) \in E}\Omega_{i,j} &= N - 1 \\ \sum_{i\lt j \in V}\Omega_{i,j} &= N\sum_{k=1}^{N-1} \lambda_k^{-1} \end{align} }[/math]

where the [math]\displaystyle{ \lambda_{k} }[/math] 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 be expressed as a function of the set of spanning trees, T, of G as follows:

[math]\displaystyle{ \Omega_{i,j}=\begin{cases} \frac{\left | \{t:t \in T, e_{i,j} \in 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} }[/math]

where [math]\displaystyle{ T' }[/math] is the set of spanning trees for the graph [math]\displaystyle{ G'=(V, E+e_{i,j}) }[/math].

As a squared Euclidean distance

Since the Laplacian [math]\displaystyle{ L }[/math] is symmetric and positive semi-definite, so is [math]\displaystyle{ \left(L+\frac{1}{|V|}\Phi\right) }[/math], thus its pseudo-inverse [math]\displaystyle{ \Gamma }[/math] is also symmetric and positive semi-definite. Thus, there is a [math]\displaystyle{ K }[/math] such that [math]\displaystyle{ \Gamma = KK^\textsf{T} }[/math] and we can write:

[math]\displaystyle{ \Omega_{i,j} = \Gamma_{i,i} + \Gamma_{j,j} - \Gamma_{i,j} - \Gamma_{j,i} = K_iK_i^\textsf{T} + K_j K_j^\textsf{T} - K_i K_j^\textsf{T} - K_j K_i^\textsf{T} = \left(K_i - K_j\right)^2 }[/math]

showing that the square root of the resistance distance corresponds to the Euclidean distance in the space spanned by [math]\displaystyle{ K }[/math].

Connection with Fibonacci numbers

A fan graph is a graph on [math]\displaystyle{ n+1 }[/math] vertices where there is an edge between vertex [math]\displaystyle{ i }[/math] and [math]\displaystyle{ n+1 }[/math] for all [math]\displaystyle{ i = 1, 2, 3, ...n, }[/math] and there is an edge between vertex [math]\displaystyle{ i }[/math] and [math]\displaystyle{ i+1 }[/math] for all [math]\displaystyle{ i = 1, 2, 3, ..., n-1. }[/math]

The resistance distance between vertex [math]\displaystyle{ n + 1 }[/math] and vertex [math]\displaystyle{ i \in \{1,2,3,...,n\} }[/math] is [math]\displaystyle{ \frac{ F_{2(n-i)+1} F_{2i-1} }{ F_{2n} } }[/math] where [math]\displaystyle{ F_{j} }[/math] is the [math]\displaystyle{ j }[/math]-th Fibonacci number, for [math]\displaystyle{ j \geq 0 }[/math].[2][3]

See also

References

  1. ↑ https://mathworld.wolfram.com/ResistanceDistance.html
  2. ↑ Bapat, R. B.; Gupta, Somit (2010). "Resistance distance in wheels and fans". Indian Journal of Pure and Applied Mathematics 41: 1–13. doi:10.1007/s13226-010-0004-2. 
  3. ↑ http://www.isid.ac.in/~rbb/somitnew.pdf




Retrieved from "https://handwiki.org/wiki/index.php?title=Resistance_distance&oldid=37286"