Walks and regular integral graphs

Abstract

We establish a useful correspondence between the closed walks in regular graphs and the walks in infinite regular trees, which, after counting the walks of a given length between vertices at a given distance in an infinite regular tree, provides a lower bound on the number of closed walks in regular graphs. This lower bound is then applied to reduce the number of the feasible spectra of the 4-regular bipartite integral graphs by more than a half. Next, we give the details of the exhaustive computer search on all 4-regular bipartite graphs with up to 24 vertices, which yields a total of 47 integral graphs.