Directed strongly walk-regular graphs |
| |
Authors: | E R van Dam G R Omidi |
| |
Institution: | 1.Department of Econometrics and Operations Research,Tilburg University,Tilburg,The Netherlands;2.Department of Mathematical Sciences,Isfahan University of Technology,Isfahan,Iran;3.School of Mathematics,Institute for Research in Fundamental Sciences (IPM),Tehran,Iran |
| |
Abstract: | 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 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 \(\varGamma \) with only real eigenvalues whose adjacency matrix is not diagonalizable has at most two values of \(\ell \) for which \(\varGamma \) can be strongly \(\ell \)-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 \(\varGamma \) for which there are infinitely many \(\ell \) for which \(\varGamma \) is strongly \(\ell \)-walk-regular. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|