Spectral and Geometric Properties of k-Walk-Regular Graphs

Let us consider a connected graph G with diameter D. For a given integer k between 0 and D, we say that G is k-walk-regular if the number of walks of length ℓ between vertices u, v only depends on the distance between u and v, provided that such a distance does not exceed k. Thus, in particular, a 0-walk-regular graph is the same as a walk-regular graph, where the number of cycles of length ℓ rooted at a given vertex is a constant through all the graph. In the other extreme, the distance-regular graphs correspond to the case k = D . In this talk we discuss some algebraic characterizations of k-walk-regularity, in terms of the local spectrum and pre-distance-polynomials of G. Moreover, some results on the relationship between the diameter and the spectrum, as well as some geometric properties, of walk-regular graphs are presented.