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

DOI: 10.2140/pjm.1979.80.443

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