“School of Mathematics”
Back to Papers HomeBack to Papers of School of Mathematics
| Paper IPM / M / 16018 |
|
| 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.
Download TeX format |
|
| back to top | |
