Hostname: page-component-78c5997874-mlc7c Total loading time: 0 Render date: 2024-11-07T21:16:20.788Z Has data issue: false hasContentIssue false

Potential Theory on Distance-Regular Graphs

Published online by Cambridge University Press:  12 September 2008

Norman L. Biggs
Affiliation:
London School of Economics, Houghton St., London WC2A 2AE

Abstract

A graph may be regarded as an electrical network in which each edge has unit resistance. We obtain explicit formulae for the effective resistance of the network when a current enters at one vertex and leaves at another in the distance-regular case. A well-known link with random walks motivates a conjecture about the maximum effective resistance. Arguments are given that point to the truth of the conjecture for all known distance-regular graphs.

Type
Research Article
Copyright
Copyright © Cambridge University Press 1993

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

[1]Aldous, D. (1989) An introduction to covering problems for random walks on graphs. J. Theoretical Probability 2 87120.CrossRefGoogle Scholar
[2]Biggs, N. L. (1974) Algebraic Graph Theory, Cambridge University Press. (Revised edition to be published in 1993.)CrossRefGoogle Scholar
[3]Bollobás, B. (1979) Graph Theory: An Introductory Course, Springer-Verlag, Berlin.CrossRefGoogle Scholar
[4]Brouwer, A. E., Cohen, A. M. and Neumaier, A. (1989) Distance-Regular Graphs, Springer-Verlag, Berlin.CrossRefGoogle Scholar
[5]Doyle, P. G. and Snell, J. L. (1984) Random Walks and Electrical Networks, Math. Assoc. of America.CrossRefGoogle Scholar
[6]Foster, R. M. (1949) The average impedance of an electrical network. In: Reissner Anniversary Volume – Contributions to Applied Mechanics, J. W. Edwards, Ann Arbor, Michigan333340.Google Scholar
[7]Foster, R. M. (1961) An extension of a network theorem. IRE Trans. Circuit Theory CT-8 7576.CrossRefGoogle Scholar
[8]Nerode, A. and Shank, H. (1961) An algebraic proof of Kirchhoff's network theorem. Amer. Math. Monthly 68 244247.CrossRefGoogle Scholar
[9]Thomassen, C. (1990) Resistances and currents in infinite electrical networks. J. Comb. Theory B 49 87102.CrossRefGoogle Scholar