Resistance distance

In graph theory, the resistance distance between two vertices of a simple, connected graph, , is equal to the resistance between two equivalent points on an electrical network, constructed so as to correspond to , with each edge being replaced by a resistance of one ohm. It is a metric on graphs.

Definition

On a graph , the resistance distance between two vertices and is
:$\Omega_:=\Gamma_+\Gamma_-\Gamma_-\Gamma_,$
:where $\Gamma = \left(L + \frac\Phi\right)^+,$
with denoting the Moore–Penrose inverse, the Laplacian matrix of , is the number of vertices in , and is the matrix containing all 1s.

Properties of resistance distance

If then . For an undirected graph
:$\Omega_=\Omega_=\Gamma_+\Gamma_-2\Gamma_$

General sum rule

For any -vertex simple connected graph and arbitrary matrix :

:$\sum_(LML)_\Omega_ = -2\operatorname(ML)$

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

:$\begin \sum_\Omega_ &= N - 1 \\ \sum_\Omega_ &= N\sum_^ \lambda_k^ \end$

where the are the non-zero eigenvalues of the Laplacian matrix. This unordered sum
:$\sum_ \Omega_$
is called the Kirchhoff index of the graph.

Relationship to the number of spanning trees of a graph

For a simple connected graph , the resistance distance between two vertices may be expressed as a function of the set of spanning trees, , of as follows:

:$\Omega_=\begin \frac, & (i,j) \in E\\ \frac, &(i,j) \not \in E \end$

where is the set of spanning trees for the graph .

As a squared Euclidean distance

Since the Laplacian is symmetric and positive semi-definite, so is
:$\left(L+\frac\Phi\right),$
thus its pseudo-inverse is also symmetric and positive semi-definite. Thus, there is a such that $\Gamma = KK^\textsf$ and we can write:

:$\Omega_ = \Gamma_ + \Gamma_ - \Gamma_ - \Gamma_ = K_iK_i^\textsf + K_j K_j^\textsf - K_i K_j^\textsf - K_j K_i^\textsf = \left(K_i - K_j\right)^2$

showing that the square root of the resistance distance corresponds to the Euclidean distance in the space spanned by .

Connection with Fibonacci numbers

A fan graph is a graph on vertices where there is an edge between vertex and for all , and there is an edge between vertex and for all .

The resistance distance between vertex and vertex is
:$\frac$
where is the -th Fibonacci number, for .http://www.isid.ac.in/~rbb/somitnew.pdf

See also

* Conductance (graph)

References

*
*
*
*
*
*
*
*
*
*
*

*

* {{cite journal
, first1=Yujun
, last1=Yang
, first2=Heping
, last2=Zhang
, title=Some rules on resistance distance with applications
, journal=J. Phys. A: Math. Theor.
, year=2008
, volume=41
, issue=44
, pages=445203
, doi=10.1088/1751-8113/41/44/445203
, bibcode = 2008JPhA...41R5203Y

Electrical resistance and conductance
Graph distance