Vol. 80, No. 2, 1979

Recent Issues
Vol. 329: 1  2
Vol. 328: 1  2
Vol. 327: 1  2
Vol. 326: 1  2
Vol. 325: 1  2
Vol. 324: 1  2
Vol. 323: 1  2
Vol. 322: 1  2
Online Archive
The Journal
About the journal
Ethics and policies
Peer-review process
Submission guidelines
Submission form
Editorial board
ISSN: 1945-5844 (e-only)
ISSN: 0030-8730 (print)
Special Issues
Author index
To appear
Other MSP journals
The spectral approach to determining the number of walks in a graph

Frank Harary and Allen John Carl Schwenk

Vol. 80 (1979), No. 2, 443–449

It is well known that the number of closed walks of length n is simply the n-th moment of the adjacency matrix. We find similar spectral expressions for unrestricted (either open or closed) walks, and also for walks from any specified starting set of points to another set of terminal points. Knowledge of the number of walks in G may be applied to find the spectrum of the complement of G. In conclusion, cyclic and dihedral equivalence relations are defined for closed walks and Burnside’s lemma is used to enumerate the number of equivalence classes of both types.

Mathematical Subject Classification 2000
Primary: 05C30
Received: 25 March 1976
Published: 1 February 1979
Frank Harary
Allen John Carl Schwenk