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 resistance of one ohm. It is a metric on graphs.

Definition

edit

On a graph G, the resistance distance Ωi,j between two vertices vi and vj is[1]

 
where  

with + denotes the Moore–Penrose inverse, L the Laplacian matrix of G, |V| is the number of vertices in G, and Φ is the |V| × |V| matrix containing all 1s.

Properties of resistance distance

edit

If i = j then Ωi,j = 0. For an undirected graph

 

General sum rule

edit

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

 

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

 

where the λk are the non-zero eigenvalues of the Laplacian matrix. This unordered sum

 

is called the Kirchhoff index of the graph.

Relationship to the number of spanning trees of a graph

edit

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:

 

where T' is the set of spanning trees for the graph G' = (V, E + ei,j). In other words, for an edge  , the resistance distance between a pair of nodes   and   is the probability that the edge   is in a random spanning tree of  .

Relationship to random walks

edit

The resistance distance between vertices   and   is proportional to the commute time   of a random walk between   and  . The commute time is the expected number of steps in a random walk that starts at  , visits  , and returns to  . For a graph with   edges, the resistance distance and commute time are related as  .[2]

As a squared Euclidean distance

edit

Since the Laplacian L is symmetric and positive semi-definite, so is

 

thus its pseudo-inverse Γ is also symmetric and positive semi-definite. Thus, there is a K such that   and we can write:

 

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

Connection with Fibonacci numbers

edit

A fan graph is a graph on n + 1 vertices where there is an edge between vertex i and n + 1 for all i = 1, 2, 3, …, n, and there is an edge between vertex i and i + 1 for all i = 1, 2, 3, …, n – 1.

The resistance distance between vertex n + 1 and vertex i ∈ {1, 2, 3, …, n} is

 

where Fj is the j-th Fibonacci number, for j ≥ 0.[3]

See also

edit

References

edit
  1. ^ "Resistance Distance".
  2. ^ Chandra, Ashok K and Raghavan, Prabhakar and Ruzzo, Walter L and Smolensky, Roman (1989). "The electrical resistance of a graph captures its commute and cover times". Proceedings of the twenty-first annual ACM symposium on Theory of computing - STOC '89. pp. 574–685. doi:10.1145/73007.73062. ISBN 0897913078.{{cite book}}: CS1 maint: multiple names: authors list (link)
  3. ^ Bapat, R. B.; Gupta, Somit (2010). "Resistance distance in wheels and fans" (PDF). Indian Journal of Pure and Applied Mathematics. 41 (1): 1–13. doi:10.1007/s13226-010-0004-2. MR 2650096.