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.

Definition

On a graph G, the resistance distance Ω_i,j between two vertices v_i and v_j 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 = (V, E) 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<j\in V}}\Omega _{{i,j}}=N\sum _{{k=1}}^{{N-1}}\lambda _{{k}}^{{-1}}

where the $\lambda _{k}$ 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 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 =KK^{T}$ and we can write:

\Omega _{{i,j}}=\Gamma _{{i,i}}+\Gamma _{{j,j}}-\Gamma _{{i,j}}-\Gamma _{{j,i}}=K_{i}K_{i}^{T}+K_{j}K_{j}^{T}-K_{i}K_{j}^{T}-K_{j}K_{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]

References

↑ "Resistance distance in wheels and fans". Indian Journal of Pure and Applied Mathematics. 41: 1–13. doi:10.1007/s13226-010-0004-2.
↑ http://www.isid.ac.in/~rbb/somitnew.pdf

Klein, D. J.; Randic, M. J. (1993). "Resistance Distance". J. Math. Chem. 12: 81–95. doi:10.1007/BF01164627.
Gutman, Ivan; Mohar, Bojan (1996). "The quasi-Wiener and the Kirchhoff indices coincide". J. Chem. Inf. Comput. Sci. 36: 982–985. doi:10.1021/ci960007t.
Palacios, Jose Luis (2001). "Closed-form formulas for the Kirchhoff index". Int. J. Quant. Chem. 81: 135–140. doi:10.1002/1097-461X(2001)81:2<135::AID-QUA4>3.0.CO;2-G.
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. doi:10.1002/qua.10057.
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. Bibcode:2003ZNatA..58..494B. doi:10.1515/zna-2003-9-1003.
Placios, Jose Luis (2004). "Foster's formulas via probability and the Kirchhoff index". Method. Comput. Appl. Probab. 6 (4): 381–387. doi:10.1023/B:MCAP.0000045086.76839.54.
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. Bibcode:2008IJQC..108.1200B. doi:10.1002/qua.21588.
Zhou, Bo; Trinajstic, Nenad (2009). "The Kirchhoff index and the matching number". Int. J. Quant. Chem. 109: 2978–2981. Bibcode:2009IJQC..109.2978Z. doi:10.1002/qua.21915.
Zhou, Bo; Trinajstic, Nenad (2009). "On resistance-distance and the Kirchhoff index". J. Math. Chem. 46: 283–289. doi:10.1007/s10910-008-9459-3.
Zhou, Bo. "On sum of powers of Laplacian eigenvalues and Laplacian Estrada Index of graphs". arXiv:1102.1144.

Zhang, Heping; Yang, Yujun (2007). "Resistance distance and Kirchhoff index in circulant graphs". Int. J. Quantum Chem. 107: 330–339. Bibcode:2007IJQC..107..330Z. doi:10.1002/qua.21068.

Yang, Yujun; Zhang, Heping (2008). "Some rules on resistance distance with applications". J. Phys. A: Math. Theor. 41: 445203. Bibcode:2008JPhA...41R5203Y. doi:10.1088/1751-8113/41/44/445203.

This article is issued from Wikipedia - version of the 10/12/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.