Characterizing (l, m)-walk-regular graphs

A graph G with diameter D and d + 1 distinct eigenvalues is said to be (l, m)-walk-regular, for some integers l is an element of [0,d] and m is an element of [0,D], l >= m, if the number of walks of length i is an element of[0,l] between any pair of vertices at distance j is an element of [0, m] depends only on the values of i and j. In this paper, we study some algebraic and combinatorial characterizations of (l, m)-walk-regularity based on the so-called predistance polynomials and the preintersection numbers. (C) 2010 Elsevier Inc. All rights reserved.