Directed strongly walk-regular graphs

Edwin van Dam, G.R. Omidi

Research output: Contribution to journalArticleScientificpeer-review

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.
Original languageEnglish
Pages (from-to)623–639
JournalJournal of Algebraic Combinatorics
Volume47
Issue number4
DOIs
Publication statusPublished - 1 Jun 2018

Fingerprint

Regular Graph
Walk
Digraph
Eigenvalue
Adjacency Matrix
Vertex of a graph
Adjacent
Generalise
Directed Graph
Regularity

Keywords

  • Strongly regular digraph
  • Walk
  • Spectrum
  • Eigenvalues

Cite this

van Dam, Edwin ; Omidi, G.R. / Directed strongly walk-regular graphs. In: Journal of Algebraic Combinatorics. 2018 ; Vol. 47, No. 4. pp. 623–639.
@article{b52c84f58d17448ab2e1bdf1a1990aa0,
title = "Directed strongly walk-regular graphs",
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.",
keywords = "Strongly regular digraph, Walk, Spectrum, Eigenvalues",
author = "{van Dam}, Edwin and G.R. Omidi",
year = "2018",
month = "6",
day = "1",
doi = "10.1007/s10801-017-0789-8",
language = "English",
volume = "47",
pages = "623–639",
journal = "Journal of Algebraic Combinatorics",
issn = "0925-9899",
publisher = "Springer Netherlands",
number = "4",

}

Directed strongly walk-regular graphs. / van Dam, Edwin; Omidi, G.R.

In: Journal of Algebraic Combinatorics, Vol. 47, No. 4, 01.06.2018, p. 623–639.

Research output: Contribution to journalArticleScientificpeer-review

TY - JOUR

T1 - Directed strongly walk-regular graphs

AU - van Dam, Edwin

AU - Omidi, G.R.

PY - 2018/6/1

Y1 - 2018/6/1

N2 - 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.

AB - 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.

KW - Strongly regular digraph

KW - Walk

KW - Spectrum

KW - Eigenvalues

U2 - 10.1007/s10801-017-0789-8

DO - 10.1007/s10801-017-0789-8

M3 - Article

VL - 47

SP - 623

EP - 639

JO - Journal of Algebraic Combinatorics

JF - Journal of Algebraic Combinatorics

SN - 0925-9899

IS - 4

ER -