Normally regular digraphs (Q888636)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Normally regular digraphs |
scientific article |
Statements
Normally regular digraphs (English)
0 references
2 November 2015
0 references
Summary: A normally regular digraph with parameters (\(v,k,\lambda,\mu\)) is a directed graph on \(v\) vertices whose adjacency matrix \(A\) satisfies the equation \(AA^t=k I+\lambda (A+A^t)+\mu(J-I-A-A^t)\). This means that every vertex has out-degree \(k\), a pair of non-adjacent vertices have \(\mu\) common out-neighbours, a pair of vertices connected by an edge in one direction have \(\lambda\) common out-neighbours and a pair of vertices connected by edges in both directions have \(2\lambda-\mu\) common out-neighbours. We often assume that two vertices can not be connected in both directions. We prove that the adjacency matrix of a normally regular digraph is normal. A connected \(k\)-regular digraph with normal adjacency matrix is a normally regular digraph if and only if all eigenvalues other than \(k\) are on one circle in the complex plane. We prove several non-existence results, structural characterizations, and constructions of normally regular digraphs. In many cases these graphs are Cayley graphs of abelian groups and the construction is then based on a generalization of difference sets.{ }We also show connections to other combinatorial objects: strongly regular graphs, symmetric 2-designs and association schemes.
0 references
directed graphs
0 references
design theory
0 references
association schemes
0 references