World Library  
Flag as Inappropriate
Email this Article

Resistance distance

Article Id: WHEBN0000695230
Reproduction Date:

Title: Resistance distance  
Author: World Heritage Encyclopedia
Language: English
Subject: Graph theory, Table of simple cubic graphs, Conductance (graph), Series and parallel circuits, Electrical impedance
Collection: Graph Theory
Publisher: World Heritage Encyclopedia
Publication
Date:
 

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.

Contents

  • Definition 1
  • Properties of resistance distance 2
    • General sum rule 2.1
    • Relationship to the number of spanning trees of a graph 2.2
    • As a squared Euclidean distance 2.3
    • Connection with Fibonacci numbers 2.4
  • See also 3
  • References 4

Definition

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

\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

\Omega_{i,j}=0.\,

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 = (VE) and arbitrary N×N matrix M:

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

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

\sum_{(i,j) \in E}\Omega_{i,j}=N-1
\sum_{i

where the \lambda_{k} are the non-zero eigenvalues of the Laplacian matrix. This unordered sum ΣiΩ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 = (VE), 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} \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}

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

As a squared Euclidean distance

Since the Laplacian L is symmetric and positive semi-definite, its pseudoinverse \Gamma is also symmetric and positive semi-definite. Thus, there is a K such that \Gamma = K K^T and we can write:

\Omega_{i,j} = \Gamma_{i,i}+\Gamma_{j,j}-\Gamma_{i,j}-\Gamma_{j,i} = K_iK_i^T + K_jK_j^T - K_iK_j^T - K_jK_i^T = (K_i - K_j)^2

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

Connection with Fibonacci numbers

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 \in \{1,2,3,...,n\} is \frac{ F_{2(n-i)+1} F_{2i-1} }{ F_{2n} } where F_{j} is the j-th Fibonacci number, for j \geq 0.[1][2]

See also

References

  1. ^ http://link.springer.com/article/10.1007/s13226-010-0004-2
  2. ^ http://www.isid.ac.in/~rbb/somitnew.pdf
  • Klein, D. J.; Randic, M. J. (1993). "Resistance Distance". J. Math. Chem. 12: 81.  
  • Gutman, Ivan; Mohar, Bojan (1996). "The quasi-Wiener and the Kirchhoff indices coincide". J. Chem. Inf. Comput. Sci. 36: 982–985.  
  • Palacios, Jose Luis (2001). "Closed-form formulas for the Kirchhoff index". Int. J. Quant. Chem. 81: 135–140.  
  • Babic, D.; Klein, D. J.; Lukovits, I.; Nikolic, S.; Trinajstic, N. (2002). "Resistance-distance matrix: a computational algorithm and its application". Int. J. Quant. Chem. 90 (1): 166–167.  
  • Klein, D. J. (2002). "Resistance Distance Sum Rules" (PDF). Croatica Chem. Acta 75 (2): 633–649. 
  • Bapat, Ravindra B.; Gutman, Ivan; Xiao, Wenjun (2003). "A simple method for computing resistance distance". Z. Naturforsch. 58a: 494–498.  
  • Placios, Jose Luis (2004). "Foster's formulas via probability and the Kirchhoff index". Method. Comput. Appl. Probab. 6 (4): 381–387.  
  • Bendito, Enrique; Carmona, Angeles; Encinas, Andres M.; Gesto, Jose M. (2008). "A formula for the Kirhhoff index". Int. J. Quant. Chem. 108 (6): 1200–1206.  
  • Zhou, Bo; Trinajstic, Nenad (2009). "The Kirchhoff index and the matching number". Int. J. Quant. Chem. 109: 2978–2981.  
  • Zhou, Bo; Trinajstic, Nenad (2009). "On resistance-distance and the Kirchhoff index". J. Math. Chem. 46: 283–289.  
  • Zhou, Bo. "On sum of powers of Laplacian eigenvalues and Laplacian Estrada Index of graphs".  
  • Zhang, Heping; Yang, Yujun (2007). "Resistance distance and Kirchhoff index in circulant graphs". Int. J. Quantum Chem. 107: 330–339.  
  • Yang, Yujun; Zhang, Heping (2008). "Some rules on resistance distance with applications". J. Phys. A: Math. Theor. 41: 445203.  
This article was sourced from Creative Commons Attribution-ShareAlike License; additional terms may apply. World Heritage Encyclopedia content is assembled from numerous content providers, Open Access Publishing, and in compliance with The Fair Access to Science and Technology Research Act (FASTR), Wikimedia Foundation, Inc., Public Library of Science, The Encyclopedia of Life, Open Book Publishers (OBP), PubMed, U.S. National Library of Medicine, National Center for Biotechnology Information, U.S. National Library of Medicine, National Institutes of Health (NIH), U.S. Department of Health & Human Services, and USA.gov, which sources content from all federal, state, local, tribal, and territorial government publication portals (.gov, .mil, .edu). Funding for USA.gov and content contributors is made possible from the U.S. Congress, E-Government Act of 2002.
 
Crowd sourced content that is contributed to World Heritage Encyclopedia is peer reviewed and edited by our editorial staff to ensure quality scholarly research articles.
 
By using this site, you agree to the Terms of Use and Privacy Policy. World Heritage Encyclopedia™ is a registered trademark of the World Public Library Association, a non-profit organization.
 



Copyright © World Library Foundation. All rights reserved. eBooks from Hawaii eBook Library are sponsored by the World Library Foundation,
a 501c(4) Member's Support Non-Profit Organization, and is NOT affiliated with any governmental agency or department.