## Directed strongly walk-regular graphs. (arXiv:1508.05281v2 [math.CO] UPDATED)

We generalize the concept of strong walk-regularity to directed graphs. We
call a digraph strongly $\ell$-walk-regular with $\ell >1$ if the number of
walks of length $\ell$ from a vertex to another vertex depends only on whether
the two vertices are the same, adjacent, or not adjacent. This generalizes also
the well-studied strongly regular digraphs and a problem posed by Hoffman. Our
main tools are eigenvalue methods. The case that the adjacency matrix is
diagonalizable with only real eigenvalues resembles the undirected case. We
show that a digraph $\Gamma$ with only real eigenvalues whose adjacency matrix
is not diagonalizable has at most two values of $\ell$ for which $\Gamma$ can
be strongly $\ell$-walk-regular, and we also construct examples of such
strongly walk-regular digraphs. We also consider digraphs with nonreal
eigenvalues. We give such examples and characterize those digraphs $\Gamma$ for
which there are infinitely many $\ell$ for which $\Gamma$ is strongly
$\ell$-wa查看全文