“School of Mathematics”

Back to Papers Home
Back to Papers of School of Mathematics

Paper   IPM / M / 16018
School of Mathematics
  Title:   Directed strongly walk-regular graphs
  Author(s):  Gholam Reza Omidi (Joint with E. R. van Dam)
  Status:   Publishied
  Journal: J. Algebraic Combin.
  Vol.:  47
  Year:  2018
  Pages:   623-639
  Supported by:  IPM
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
scroll left or right