Normally Regular Digraphs

作者：Jorgensen Leif K^*

来源：ELECTRONIC JOURNAL OF COMBINATORICS, 2015, 22(4): P4.21.

DOI：10.37236/4798

A normally regular digraph with parameters (v, k, A, lambda, mu) is a directed graph on v vertices whose adjacency matrix A satisfies the equation AA(t) = kI + lambda(A + A(t)) + mu(J - I - A - A(t)). This means that every vertex has out-degree k, a pair of nonadjacent vertices have lambda common out-neighbours, a pair of vertices connected by an edge in one direction have A 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

• 出版日期2015-10-30