×

On \(k\)-walk-regular graphs. (English) Zbl 1226.05107

Summary: Considering a connected graph \(G\) with diameter \(D\), we say that it is \(k\)-walk-regular, for a given integer \(k\) (\(0\leq k \leq D\)), if the number of walks of length \(\ell\) between any pair of vertices only depends on the distance between them, provided that this distance does not exceed \(k\). Thus, for \(k=0\), this definition coincides with that of walk-regular graph, where the number of cycles of length \(\ell\) rooted at a given vertex is a constant through all the graph. In the other extreme, for \(k=D\), we get one of the possible definitions for a graph to be distance-regular. In this paper we show some algebraic characterizations of \(k\)-walk-regularity, which are based on the so-called local spectrum and predistance polynomials of \(G\).

MSC:

05C12 Distance in graphs
05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)
05E30 Association schemes, strongly regular graphs
05C25 Graphs and abstract algebra (groups, rings, fields, etc.)
PDFBibTeX XMLCite
Full Text: EuDML EMIS