“School of Mathematics”
Back to Papers HomeBack to Papers of School of Mathematics
Paper IPM / M / 16018  


Abstract:  
We generalize the concept of strong walkregularity to directed graphs. We call a digraph strongly ï¿½??walkregular 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 wellstudied 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 ï¿½??walkregular, and we also construct examples of such strongly walkregular digraphs. We also consider digraphs with nonreal eigenvalues. We give such examples and characterize those digraphs ï¿½? for which there are infinitely many ï¿½?? for which ï¿½? is strongly ï¿½??walkregular.
Download TeX format 

back to top 