4
$\begingroup$

An undirected graph may be regarded as a resistor network where each edge corresponds to a resistor of unit resistance. This paper covers such an approach.

I paraphrase some statements from Chapter 3 of this paper.


Consider a graph $G$ as a resistor network where each edge is a unit resistance. To compute the effective resistance between two vertices $u$ and $v$, assume that a battery of voltage $V$ is attached to $u$ and $v$ producing a current through the graph. The current flowing through the circuit can be determined by calculating the voltage at each point on the graph. A function $f$ on the vertex set $V$ of $G$ is harmonic at a point $z\in V$ if $f(z)$ is the average of neighboring values of f; that is, \begin{equation*} \sum_{\text{for any $x$ adjacent to $z$}}\big(f(x)-f(z)\big) = 0. \end{equation*} The voltage function on V can be characterized as the unique function which is harmonic on $V − \{u, v\}$ having the prescribed values on $u$ and $v$.


I'd like to use this characterization on my research. But I cannot find a reference for this 'harmonic characterization' on any other textbook. Even the above paper doesn't cite any reference for this statement. I skim through many graph theory textbooks (such as Bollobas) but in vain.

Is this characterization true? Which textbooks or papers can I use as a reference?

$\endgroup$
4
  • $\begingroup$ Kemeny and Snell: Denumerable Markov Chains? $\endgroup$ Commented Oct 1, 2016 at 9:50
  • 1
    $\begingroup$ @AnthonyQuas Doyle and Snell is probably an easier read. $\endgroup$
    – Igor Rivin
    Commented Oct 1, 2016 at 10:09
  • $\begingroup$ @IgorRivin: I think that is the book that I was thinking of. $\endgroup$ Commented Oct 1, 2016 at 10:31
  • $\begingroup$ Nice question. But be careful: see xkcd.com/356 $\endgroup$
    – Joël
    Commented Oct 6, 2016 at 19:07

3 Answers 3

5
$\begingroup$

If I am reading correctly, this appears as Theorem 1.15 of Geoffrey Grimmett's book Probability on Graphs.

It is available for free on Grimmett's web site and has also been published by Cambridge University Press.

$\endgroup$
3
$\begingroup$

My prefered reference for the subject is David's Wagner lecture notes:

https://www.math.uwaterloo.ca/~dgwagner/Networks.pdf

$\endgroup$
1
$\begingroup$

"Random walks and electric networks" by Doyle and Snell is where I learned it. I'm glad if you found our paper interesting.

$\endgroup$
1
  • $\begingroup$ Actually I could use some help on a fragment of a paper I have on this topic. If you (or anyone else) is working on electric resistance and random walks on graphs, and is interested to hear about the project, please drop me a line (just google me to find email address). $\endgroup$ Commented Apr 11, 2020 at 3:06

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .