Resistance distance

Last updated November 16, 2023

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

On a graph $G$ , the resistance distance $Ω i, j$ between two vertices $v i$ and $v j$ is^[1]

\Omega _{i,j}:=\Gamma _{i,i}+\Gamma _{j,j}-\Gamma _{i,j}-\Gamma _{j,i},

where

\Gamma =\left(L+{\frac {1}{|V|}}\Phi \right)^{+},

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

Properties of resistance distance

If $i = j$ then $Ω 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 \times 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;

{\begin{aligned}\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}\end{aligned}}

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

\sum _{i<j}\Omega _{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 be 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)$ . In other words, for an edge $(i,j)\in E$ , the resistance distance between a pair of nodes $i$ and $j$ is the probability that the edge $(i,j)$ is in a random spanning tree of $G$ .

Relationship to random walks

The resistance distance between vertices $u$ and $u$ is proportional to the commute time $C_{u,v}$ of a random walk between $u$ and $v$ . The commute time is the expected number of steps in a random walk that starts at $u$ , visits $v$ , and returns to $u$ . For a graph with $m$ edges, the resistance distance and commute time are related as $C_{u,v}=2m\Omega _{u,v}$ .^[2]

As a squared Euclidean distance

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

\left(L+{\frac {1}{|V|}}\Phi \right),

thus its pseudo-inverse $Γ$ is also symmetric and positive semi-definite. Thus, there is a $K$ such that $\Gamma =KK^{\textsf {T}}$ and we can write:

\Omega _{i,j}=\Gamma _{i,i}+\Gamma _{j,j}-\Gamma _{i,j}-\Gamma _{j,i}=K_{i}K_{i}^{\textsf {T}}+K_{j}K_{j}^{\textsf {T}}-K_{i}K_{j}^{\textsf {T}}-K_{j}K_{i}^{\textsf {T}}=\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 $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, \dots, n$ , and there is an edge between vertex $i$ and $i + 1$ for all $i = 1, 2, 3, \dots, n - 1$ .

The resistance distance between vertex $n + 1$ and vertex $i \in {1, 2, 3, \dots, 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$ .^[3]^[4]

Related Research Articles

In mathematics, especially representation theory, a quiver is another name for a multidigraph; that is, a directed graph where loops and multiple arrows between two vertices are allowed. Quivers are commonly used in representation theory: a representation $V$ of a quiver assigns a vector space $V (x)$ to each vertex $x$ of the quiver and a linear map $V (a)$ to each arrow $a$ .

In mathematics, an incidence matrix is a logical matrix that shows the relationship between two classes of objects, usually called an incidence relation. If the first class is X and the second is Y, the matrix has one row for each element of X and one column for each element of Y. The entry in row x and column y is 1 if x and y are related and 0 if they are not. There are variations; see below.

In mathematics, and specifically differential geometry, a connection form is a manner of organizing the data of a connection using the language of moving frames and differential forms.

In mathematics, loop-erased random walk is a model for a random simple path with important applications in combinatorics, physics and quantum field theory. It is intimately connected to the uniform spanning tree, a model for a random tree. See also random walk for more general treatment of this topic.

In the mathematical field of graph theory, Kirchhoff's theorem or Kirchhoff's matrix tree theorem named after Gustav Kirchhoff is a theorem about the number of spanning trees in a graph, showing that this number can be computed in polynomial time from the determinant of a submatrix of the Laplacian matrix of the graph; specifically, the number is equal to any cofactor of the Laplacian matrix. Kirchhoff's theorem is a generalization of Cayley's formula which provides the number of spanning trees in a complete graph.

In mathematics, the discrete Laplace operator is an analog of the continuous Laplace operator, defined so that it has meaning on a graph or a discrete grid. For the case of a finite-dimensional graph, the discrete Laplace operator is more commonly called 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 Laplacian matrix can be viewed as a matrix form of the negative discrete Laplace operator on a graph approximating the negative continuous Laplacian obtained by the finite difference method.

<span class="mw-page-title-main">Dominating set</span> Subset of a graphs nodes such that all other nodes link to at least one

In graph theory, a dominating set for a graph $G$ is a subset $D$ of its vertices, such that any vertex of $G$ is either in $D$ , or has a neighbor in $D$ . The domination number $γ(G)$ is the number of vertices in a smallest dominating set for $G$ .

<span class="mw-page-title-main">Cartesian product of graphs</span> Operation in graph theory

In graph theory, the Cartesian product $G □ H$ of graphs $G$ and $H$ is a graph such that:

Graph pebbling is a mathematical game played on a graph with zero or more pebbles on each of its vertices. 'Game play' is composed of a series of pebbling moves. A pebbling move on a graph consists of choosing a vertex with at least two pebbles, removing two pebbles from it, and adding one to an adjacent vertex (the second removed pebble is discarded from play). π(G), the pebbling number of a graph G, is the lowest natural number n that satisfies the following condition:

Given any target or 'root' vertex in the graph and any initial configuration of n pebbles on the graph, it is possible, after a series of pebbling moves, to reach a new configuration in which the designated root vertex has one or more pebbles.

<span class="mw-page-title-main">Abelian sandpile model</span> Cellular automaton

The Abelian sandpile model (ASM) is the more popular name of the original Bak–Tang–Wiesenfeld model (BTW). BTW model was the first discovered example of a dynamical system displaying self-organized criticality. It was introduced by Per Bak, Chao Tang and Kurt Wiesenfeld in a 1987 paper.

In mathematics, the Kontsevich quantization formula describes how to construct a generalized ★-product operator algebra from a given arbitrary finite-dimensional Poisson manifold. This operator algebra amounts to the deformation quantization of the corresponding Poisson algebra. It is due to Maxim Kontsevich.

In matroid theory, a field within mathematics, a gammoid is a certain kind of matroid, describing sets of vertices that can be reached by vertex-disjoint paths in a directed graph.

In graph theory, the Lovász number of a graph is a real number that is an upper bound on the Shannon capacity of the graph. It is also known as Lovász theta function and is commonly denoted by $, using a script form of the Greek letter theta to contrast with the upright theta used for Shannon capacity. This quantity was first introduced by László Lovász in his 1979 paper On the Shannon Capacity of a Graph .$

In the geometry of numbers, the Klein polyhedron, named after Felix Klein, is used to generalize the concept of continued fractions to higher dimensions.

In Mathematics, the Lindström–Gessel–Viennot lemma provides a way to count the number of tuples of non-intersecting lattice paths, or, more generally, paths on a directed graph. It was proved by Gessel–Viennot in 1985, based on previous work of Lindström published in 1973.

In computer science, a suffix automaton is an efficient data structure for representing the substring index of a given string which allows the storage, processing, and retrieval of compressed information about all its substrings. The suffix automaton of a string $is the smallest directed acyclic graph with a dedicated initial vertex and a set of "final" vertices, such that paths from the initial vertex to final vertices represent the suffixes of the string.$

In mathematics, topological recursion is a recursive definition of invariants of spectral curves. It has applications in enumerative geometry, random matrix theory, mathematical physics, string theory, knot theory.

In graph theory a minimum spanning tree (MST) $of a graph with and is a tree subgraph of that contains all of its vertices and is of minimum weight.$

The counting lemmas this article discusses are statements in combinatorics and graph theory. The first one extracts information from $-regular pairs of subsets of vertices in a graph, in order to guarantee patterns in the entire graph; more explicitly, these patterns correspond to the count of copies of a certain graph in . The second counting lemma provides a similar yet more general notion on the space of graphons, in which a scalar of the cut distance between two graphs is correlated to the homomorphism density between them and .$

References

↑ "Resistance Distance".
↑ 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)
↑ Bapat, R. B.; Gupta, Somit (2010). "Resistance distance in wheels and fans". Indian Journal of Pure and Applied Mathematics. 41: 1–13. CiteSeerX 10.1.1.418.7626 . doi:10.1007/s13226-010-0004-2. S2CID 14807374.
↑ http://www.isid.ac.in/~rbb/somitnew.pdf ^{[ bare URL PDF ]}

Klein, D. J.; Randic, M. J. (1993). "Resistance Distance". J. Math. Chem. 12: 81–95. doi:10.1007/BF01164627. S2CID 16382100.
Gutman, Ivan; Mohar, Bojan (1996). "The quasi-Wiener and the Kirchhoff indices coincide". J. Chem. Inf. Comput. Sci. 36 (5): 982–985. doi:10.1021/ci960007t.
Palacios, Jose Luis (2001). "Closed-form formulas for the Kirchhoff index". Int. J. Quantum Chem. 81 (2): 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. Quantum 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. Archived from the original (PDF) on 2012-03-26.
Bapat, Ravindra B.; Gutman, Ivan; Xiao, Wenjun (2003). "A simple method for computing resistance distance". Z. Naturforsch. 58a (9–10): 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. S2CID 120309331.
Bendito, Enrique; Carmona, Angeles; Encinas, Andres M.; Gesto, Jose M. (2008). "A formula for the Kirchhoff index". Int. J. Quantum 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. Quantum Chem. 109 (13): 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. hdl: 10338.dmlcz/140814 . S2CID 119389248.
Zhou, Bo (2011). "On sum of powers of Laplacian eigenvalues and Laplacian Estrada Index of graphs". Match Commun. Math. Comput. Chem. 62: 611–619. arXiv: 1102.1144 .

Zhang, Heping; Yang, Yujun (2007). "Resistance distance and Kirchhoff index in circulant graphs". Int. J. Quantum Chem. 107 (2): 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 (44): 445203. Bibcode:2008JPhA...41R5203Y. doi:10.1088/1751-8113/41/44/445203. S2CID 122226781.

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[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". Indian Journal of Pure and Applied Mathematics. 41: 1–13. CiteSeerX 10.1.1.418.7626 . doi:10.1007/s13226-010-0004-2. S2CID 14807374.

[4] ttp://www.isid.ac.in/~rbb/somitnew.pdf ^{[ bare URL PDF ]}

[1]

[2]

[3]

[4]