### Abstract

We generalize the concept of strong walk-regularity to directed graphs. We call a digraph strongly ℓ -walk-regular with ℓ>1 if the number of walks of length ℓ from a vertex to another vertex depends only on whether the first vertex is the same as, adjacent to, or not adjacent to the second vertex. 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 Γ with only real eigenvalues whose adjacency matrix is not diagonalizable has at most two values of ℓ for which Γ can be strongly ℓ -walk-regular, and we also construct examples of such strongly walk-regular digraphs. We also consider digraphs with non-real eigenvalues. We give such examples and characterize those digraphs Γ for which there are infinitely many ℓ for which Γ is strongly ℓ -walk-regular.

Original language | English |
---|---|

Pages (from-to) | 623–639 |

Journal | Journal of Algebraic Combinatorics |

Volume | 47 |

Issue number | 4 |

DOIs | |

Publication status | Published - 1 Jun 2018 |

### Keywords

- Strongly regular digraph
- Walk
- Spectrum
- Eigenvalues

## Fingerprint Dive into the research topics of 'Directed strongly walk-regular graphs'. Together they form a unique fingerprint.

## Cite this

van Dam, E., & Omidi, G. R. (2018). Directed strongly walk-regular graphs.

*Journal of Algebraic Combinatorics*,*47*(4), 623–639. https://doi.org/10.1007/s10801-017-0789-8