Directed strongly walk-regular graphs

DOI10.1007/S10801-017-0789-8MaRDI QIDQ1668674zbMATH OpenOpenAlexWikidataFDO

Authors Edwin R. Van Dam, G. R. Omidi

Publication date 29 August 2018

Published in Journal of Algebraic Combinatorics (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/1508.05281

zbMATH Keywords

eigenvaluesspectrumstrongly regular digraphwalk

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Association schemes, strongly regular graphs (05E30)

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 two vertices are the same, adjacent, or not adjacent. 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 $Gamma$ with only real eigenvalues whose adjacency matrix is not diagonalizable has at most two values of $ell$ for which $Gamma$ can be strongly $ell$-walk-regular, and we also construct examples of such strongly walk-regular digraphs. We also consider digraphs with nonreal eigenvalues. We give such examples and characterize those digraphs $Gamma$ for which there are infinitely many $ell$ for which $Gamma$ is strongly $ell$-walk-regular.

Recommendations

• Strongly walk-regular graphs
• Walk regular digraphs.
• On (l,m)-walk-regular digraphs.
• k-walk-regular digraphs
• The walk-regular invariability of walk-regular digraphs

Cites work

• A directed graph version of strongly regular graphs
• Directed graphs with unique paths of fixed length
• Directed strongly regular graphs with =
• Distance-transitive and distance-regular digraphs
• Generating regular directed graphs
• scientific article; zbMATH DE number 5130692 (Why is no real title available?)
• scientific article; zbMATH DE number 3588689 (Why is no real title available?)
• scientific article; zbMATH DE number 1355278 (Why is no real title available?)
• On some solutions of A^k=dI+ J
• Representations of directed strongly regular graphs
• Spectra of digraphs
• Strongly walk-regular graphs
• The Polynomial of a Directed Graph
• Weakly distance-regular digraphs.

Cited in

(8)

• Small vertex-transitive directed strongly regular graphs
• Strongly walk-regular graphs
• k-walk-regular digraphs
• The walk-regular invariability of walk-regular digraphs
• Walk regular digraphs.
• On (l,m)-walk-regular digraphs.
• On the combinatorial structure and algebraic characterizations of distance-regular digraphs
• On commutative association schemes and associated (directed) graphs

This page was built for publication: Directed strongly walk-regular graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1668674)