On \(k\)-walk-regular graphs (Q1028824)

Summary: Considering a connected graph \(G\) with diameter \(D\), we say that it is \(k\)-walk-regular, for a given integer \(k\) (\(0\leq k \leq D\)), if the number of walks of length \(\ell\) between any pair of vertices only depends on the distance between them, provided that this distance does not exceed \(k\). Thus, for \(k=0\), this definition coincides with that of walk-regular graph, where the number of cycles of length \(\ell\) rooted at a given vertex is a constant through all the graph. In the other extreme, for \(k=D\), we get one of the possible definitions for a graph to be distance-regular. In this paper we show some algebraic characterizations of \(k\)-walk-regularity, which are based on the so-called local spectrum and predistance polynomials of \(G\).