Characterizing (ℓ,m)-walk-regular graphs

A graph G 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 characterizations of (ℓ,m)-walk-regularity based on the so-called predistance polynomials and the preintersection numbers.