Characterizing (ℓ,m)-walk-regular graphs

Abstract

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.

Research supported by the Ministerio de Educación y Ciencia (Spain) and the European Regional Development Fund under project MTM2008-06620-C03-01, and by the Catalan Research Council under project 2009SGR1387.