The geometry of t-spreads in k-walk-regular graphs

A graph is walk-regular if the number of closed walks of length [ell] rooted at a given vertex is a constant through all the vertices for all [ell]. For a walk-regular graph G with d+1 different eigenvalues and spectrally maximum diameter D=d, we study the geometry of its d-spreads, that is, the sets of vertices which are mutually at distance d. When these vertices are projected onto an eigenspace of its adjacency matrix, we show that they form a simplex (or tetrahedron in a three-dimensional case) and we compute its parameters. Moreover, the results are generalized to the case of k-walk-regular graphs, a family which includes both walk-regular and distance-regular graphs, and their t-spreads or vertices at distance t from each other. © 2009 Wiley Periodicals, Inc. J Graph Theory

Published by

Original source : http://dx.doi.org/10.1002%2Fjgt.20458...