Resistance distance

On a graph {{mvar|G}}, the resistance distance {{math|Ω{{sub|i,j}}}} between two vertices {{mvar|v{{sub|i}}}} and {{mvar|v{{sub|j}}}} is{{Cite web|url=https://mathworld.wolfram.com/ResistanceDistance.html|title = Resistance Distance}}

:$$

\Omega_{i,j}:=\Gamma_{i,i}+\Gamma_{j,j}-\Gamma_{i,j}-\Gamma_{j,i},

:where $\backslash Gamma\; =\; \backslash left(L\; +\; \backslash frac\{1\}$

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

If {{math|1=i = j}} then {{math|1=Ω{{sub|i,j}} = 0}}. For an undirected graph

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

For any {{mvar|N}}-vertex simple connected graph {{math|1=G = (V, E)}} and arbitrary {{math|N×N}} matrix {{mvar|M}}:

:$\backslash sum\_\{i,j\; \backslash in\; V\}(LML)\_\{i,j\}\backslash Omega\_\{i,j\}\; =\; -2\backslash operatorname\{tr\}(ML)$

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

:$\backslash begin\{align\}$

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

\sum_{i

\end{align}

where the {{mvar|λ{{sub|k}}}} are the non-zero eigenvalues of the Laplacian matrix. This unordered sum

:

is called the Kirchhoff index of the graph.

For a simple connected graph {{math|1=G = (V, E)}}, the resistance distance between two vertices may be expressed as a function of the set of spanning trees, {{mvar|T}}, of {{mvar|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 {{mvar|T'}} is the set of spanning trees for the graph {{math|1=G' = (V, E + e{{sub|i,j}})}}. In other words, for an edge $(i,j)\backslash 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$.

The resistance distance between vertices $u$ and $v$ 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\backslash Omega\_\{u,v\}$.{{cite book |last1=Chandra, Ashok K and Raghavan, Prabhakar and Ruzzo, Walter L and Smolensky, Roman |title=Proceedings of the twenty-first annual ACM symposium on Theory of computing - STOC '89 |chapter=The electrical resistance of a graph captures its commute and cover times |date=1989 |issue=21 |pages=574–685 |doi=10.1145/73007.73062 |isbn=0897913078 |chapter-url=https://dl.acm.org/doi/abs/10.1145/73007.73062}}

Resistance distance is also related to the escape probability between two vertices. The escape probability $P\_\{u,v\}$ between $u$ and $v$ is the probability that a random walk starting at $u$ visits $v$ before returning to $u$. The escape probability equals

:$$

P_{u,v} = \frac{1}{\deg(u)\Omega_{u,v}},

where $\backslash deg(u)$ is the degree of $u$.{{cite book |last1=Doyle |first1=Peter |last2=Snell |first2=J. Laurie |title=Random Walks and Electric Networks |date=1984 |publisher=American Mathematical Society |isbn=9781614440222}} Unlike the commute time, the escape probability is not symmetric in general, i.e., $P\_\{u,v\}\backslash neq\; P\_\{v,u\}$.

Since the Laplacian {{mvar|L}} is symmetric and positive semi-definite, so is

:$\backslash left(L+\backslash frac\{1\}$

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

:$\backslash Omega\_\{i,j\}\; =\; \backslash Gamma\_\{i,i\}\; +\; \backslash Gamma\_\{j,j\}\; -\; \backslash Gamma\_\{i,j\}\; -\; \backslash Gamma\_\{j,i\}\; =\; K\_iK\_i^\backslash textsf\{T\}\; +\; K\_j\; K\_j^\backslash textsf\{T\}\; -\; K\_i\; K\_j^\backslash textsf\{T\}\; -\; K\_j\; K\_i^\backslash textsf\{T\}\; =\; \backslash left(K\_i\; -\; K\_j\backslash right)^2$

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

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

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

:$\backslash frac\{\; F\_\{2(n-i)+1\}\; F\_\{2i-1\}\; \}\{\; F\_\{2n\}\; \}$

where {{mvar|F{{sub|j}}}} is the {{mvar|j}}-th Fibonacci number, for {{math|j ≥ 0}}.{{cite journal

| last1 = Bapat | first1 = R. B.

| last2 = Gupta | first2 = Somit

| doi = 10.1007/s13226-010-0004-2

| issue = 1

| journal = Indian Journal of Pure and Applied Mathematics

| mr = 2650096

| pages = 1–13

| title = Resistance distance in wheels and fans

| url = https://www.isid.ac.in/~rbb/somitnew.pdf

| volume = 41

| year = 2010}}

• Conductance (graph)

{{Reflist}}

• {{cite journal

|first1= D. J.

|last1=Klein

|first2=M. J.

|last2=Randic

|journal=J. Math. Chem.

|doi=10.1007/BF01164627

|title=Resistance Distance

|volume=12

|pages=81–95

|year=1993

|s2cid=16382100

}}

• {{cite journal

|first1=Ivan

|last1=Gutman

|first2=Bojan

|last2=Mohar

|title=The quasi-Wiener and the Kirchhoff indices coincide

|year=1996

|journal=J. Chem. Inf. Comput. Sci.

|volume=36

|issue=5

|pages=982–985

|doi=10.1021/ci960007t

}}

• {{cite journal

|title=Closed-form formulas for the Kirchhoff index

|first1=Jose Luis

|last1=Palacios

|journal=Int. J. Quantum Chem.

|year=2001

|volume=81

|issue=2

|pages=135–140

|doi=10.1002/1097-461X(2001)81:2<135::AID-QUA4>3.0.CO;2-G

}}

• {{cite journal

|first1=D.

|last1=Babic

|first2=D. J.

|last2=Klein

|first3=I.

|last3=Lukovits

|first4=S.

|last4=Nikolic

|first5=N.

|last5=Trinajstic

|title=Resistance-distance matrix: a computational algorithm and its application

|journal=Int. J. Quantum Chem.

|year=2002

|doi=10.1002/qua.10057

|volume=90

|number=1

|pages=166–167

}}

• {{cite journal

|url = http://www.stkpula.hr/ccacaa/CCA-PDF/cca2002/v75-n2/CCA_75_2002_633_649_KLEIN.pdf

|journal = Croatica Chem. Acta

|last1 = Klein

|first1 = D. J.

|title = Resistance Distance Sum Rules

|year = 2002

|volume = 75

|number = 2

|pages = 633–649

|url-status = dead

|archiveurl = https://web.archive.org/web/20120326104653/http://www.stkpula.hr/ccacaa/CCA-PDF/cca2002/v75-n2/CCA_75_2002_633_649_KLEIN.pdf

|archivedate = 2012-03-26

}}

• {{cite journal

|first1=Ravindra B.

|last1=Bapat

|first2=Ivan

|last2=Gutman

|first3=Wenjun

|last3=Xiao

|title=A simple method for computing resistance distance

|journal=Z. Naturforsch.

|year=2003

|volume=58a

|issue=9–10

|pages=494–498

|url=http://www.znaturforsch.com/aa/v58a/c58a.htm#No9

|bibcode = 2003ZNatA..58..494B |doi = 10.1515/zna-2003-9-1003 |doi-access=free

}}

• {{cite journal

|first1=Jose Luis

|last1=Placios

|title=Foster's formulas via probability and the Kirchhoff index

|journal=Method. Comput. Appl. Probab.

|year=2004

|volume=6

|number=4

|pages=381–387

|doi=10.1023/B:MCAP.0000045086.76839.54

|s2cid=120309331

}}

• {{cite journal

|first1=Enrique

|last1=Bendito

|first2=Angeles

|last2=Carmona

|first3=Andres M.

|last3=Encinas

|first4=Jose M.

|last4=Gesto

|title=A formula for the Kirchhoff index

|journal=Int. J. Quantum Chem.

|year=2008

|doi=10.1002/qua.21588

|pages=1200–1206

|volume=108

|number=6

|bibcode = 2008IJQC..108.1200B }}

• {{cite journal

|journal=Int. J. Quantum Chem.

|first1=Bo

|last1=Zhou

|title=The Kirchhoff index and the matching number

|first2=Nenad

|last2=Trinajstic

|volume=109

|issue=13

|year=2009

|pages=2978–2981

|doi=10.1002/qua.21915

|bibcode = 2009IJQC..109.2978Z }}

• {{cite journal

|first1=Bo

|last1=Zhou

|first2=Nenad

|last2=Trinajstic

|title=On resistance-distance and the Kirchhoff index

|journal=J. Math. Chem.

|year=2009

|volume=46

|pages=283–289

|doi=10.1007/s10910-008-9459-3

|hdl=10338.dmlcz/140814

|s2cid=119389248

|hdl-access=free

}}

• {{cite journal

|first1=Bo

|last1=Zhou

|title=On sum of powers of Laplacian eigenvalues and Laplacian Estrada Index of graphs

|journal=Match Commun. Math. Comput. Chem

|volume=62

|pages=611–619

|arxiv=1102.1144

|year=2011

}}

• {{cite journal

|first1=Heping

|last1=Zhang

|first2=Yujun

|last2=Yang

|title=Resistance distance and Kirchhoff index in circulant graphs

|journal=Int. J. Quantum Chem.

|year=2007

|volume=107

|issue=2

|pages=330–339

|doi=10.1002/qua.21068

|bibcode = 2007IJQC..107..330Z }}

• {{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 |s2cid=122226781

}}

Category:Electrical resistance and conductance

Category:Graph distance