Characterizing (`,m)-Walk-Regular Graphs ∗

A graph Γ with diameter D and d+1 distinct eigenvalues is said to be (`,m)-walk-regular, for some integers ` ∈ [0, d] and m ∈ [0, D], ` ≥ m, if the number of walks of length i ∈ [0, `] between any pair of vertices at distance j ∈ [0,m] depends only on the values of i and j. In this paper we study some algebraic and combinatorial char-acterizations of (`,m)-walk-regularity based on the so-called predistance polynomials and the preintersection numbers