Vol. 80, No. 2, 1979

Recent Issues
Vol. 331: 1
Vol. 330: 1  2
Vol. 329: 1  2
Vol. 328: 1  2
Vol. 327: 1  2
Vol. 326: 1  2
Vol. 325: 1  2
Vol. 324: 1  2
Online Archive
Volume:
Issue:
     
The Journal
About the journal
Ethics and policies
Peer-review process
 
Submission guidelines
Submission form
Editorial board
Officers
 
Subscriptions
 
ISSN 1945-5844 (electronic)
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
Abstract

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
Milestones
Received: 25 March 1976
Published: 1 February 1979
Authors
Frank Harary
Allen John Carl Schwenk