×

A new proof of Foster’s first theorem. (English) Zbl 1429.05104

Summary: Let \(G\) be an electrical network graph with vertex set \(V\) and edge set \(E\), and let \(\Omega(i,j)\) be the effective resistance between vertices \(i\) and \(j\) of \(G\). Foster’s first theorem [R. M. Foster, in: Reissner Annivers. Vol., Contr. Appl. Mech., Ann Arbor, Mich., 333–340 (1949; Zbl 0040.41801)] states that \(\sum_{(i,j)\in E} c_{ij} \Omega(i,j) = |V |-1\), where \(c_{ij} \) is the conductance of the edge \((i, j)\). In this note, we give a combinatorial proof of two equivalent formulae on the weighted enumeration of spanning trees of an edge-weighted graph, one of which results in a new proof of Foster’s first theorem.

MSC:

05C30 Enumeration in graph theory
05C81 Random walks on graphs
05C82 Small world graphs, complex networks (graph-theoretic aspects)

Citations:

Zbl 0040.41801
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Biggs, N., Algebraic Graph Theory (1993), Cambridge, UK: Cambridge Univ. Press, Cambridge, UK
[2] Bollobás, B., Modern Graph Theory (1998), New York, NY: Springer-Verlag, New York, NY · Zbl 0902.05016
[3] Chen, H. Y., Random walks and the effective resistance sum rules, Discrete Appl. Math, 158, 15, 1691-1700 (2010) · Zbl 1208.05136 · doi:10.1016/j.dam.2010.05.020
[4] Foster, R. M.; Edwards, J. W., Reissner Anniversary Volume, Contributions to Applied Mechanics, The average impedance of an electrical network, 333-340 (1948), Ann Arbor, MI
[5] Seshu, S.; Reed, M. B., Linear Graphs and Electrical Networks (1961), Reading, MA: Addison-Wesley, Reading, MA · Zbl 0102.34001
[6] Tetali, P., Random walks and effective resistance of networks, J. Theoret. Probab, 4, 1, 101-109 (1991) · Zbl 0722.60070 · doi:10.1007/BF01046996
[7] Tetali, P., An extension of Foster’s network theorem, Combin. Probab. Comput., 3, 3, 421-429 (1994) · Zbl 0806.60057 · doi:10.1017/S0963548300001309
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.