graph theory In mathematics, graph theory is the study of '' graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conn ...

, the resistance distance between two vertices of a simple, connected graph, , is equal to the

resistance Resistance may refer to: Arts, entertainment, and media Comics * Either of two similarly named but otherwise unrelated comic book series, both published by Wildstorm: ** ''Resistance'' (comics), based on the video game of the same title ** ''T ...

between two equivalent points on an

electrical network An electrical network is an interconnection of electrical components (e.g., batteries, resistors, inductors, capacitors, switches, transistors) or a model of such an interconnection, consisting of electrical elements (e.g., voltage sour ...

, constructed so as to correspond to , with each edge being replaced by a

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 In the mathematical field of graph theory, the Laplacian matrix, also called the graph Laplacian, admittance matrix, Kirchhoff matrix or discrete Laplacian, is a matrix representation of a graph. Named after Pierre-Simon Laplace, the graph Laplac ...

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 Matrix most commonly refers to: * ''The Matrix'' (franchise), an American media franchise ** '' The Matrix'', a 1999 science-fiction action film ** "The Matrix", a fictional setting, a virtual reality environment, within ''The Matrix'' (franchi ...

: :

\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 In linear algebra, an eigenvector () or characteristic vector of a linear transformation is a nonzero vector that changes at most by a scalar factor when that linear transformation is applied to it. The corresponding eigenvalue, often denoted b ...

of the

. 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

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