Normally regular digraphs

MaRDI QIDQ888636zbMATH OpenFDO

Authors N. E. Zubov

Publication date 2 November 2015

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1410.8424, http://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i4p21

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

association schemesdesign theorydirected graphs

Mathematics Subject Classification ID

Combinatorial aspects of block designs (05B05) Directed graphs (digraphs), tournaments (05C20) Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Association schemes, strongly regular graphs (05E30)

Abstract: A normally regular digraph with parameters $(v,k,lambda,mu)$ is a directed graph on $v$ vertices whose adjacency matrix $A$ satisfies the equation $A{A}^t=kI+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 $2lambda-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.

Review text

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.

Recommendations

• Minimum arc-cuts of normally regular digraphs and Deza digraphs
• Classification of regular digraphs, normally regular digraphs, and strongly regular digraphs
• A directed graph version of strongly regular graphs
• scientific article; zbMATH DE number 25783
• scientific article; zbMATH DE number 94924

Cites work

• A directed graph version of strongly regular graphs
• A Family of Difference Sets
• A survey of partial difference sets
• Algorithmic approach to non-symmetric 3-class association schemes
• Certain distance-regular digraphs and related rings of characteristic 4
• Deza digraphs
• Distance-transitive and distance-regular digraphs
• Doubly regular asymmetric digraphs
• Doubly regular digraphs and symmetric designs
• Doubly regular tournaments are equivalent to skew Hadamard matrices
• Feasibility conditions for non-symmetric 3-class association schemes
• Four-class skew-symmetric association schemes
• scientific article; zbMATH DE number 1600999 (Why is no real title available?)
• scientific article; zbMATH DE number 3884178 (Why is no real title available?)
• scientific article; zbMATH DE number 4150195 (Why is no real title available?)
• scientific article; zbMATH DE number 3908438 (Why is no real title available?)
• scientific article; zbMATH DE number 3943824 (Why is no real title available?)
• scientific article; zbMATH DE number 841664 (Why is no real title available?)
• scientific article; zbMATH DE number 4195995 (Why is no real title available?)
• scientific article; zbMATH DE number 3307345 (Why is no real title available?)
• Non-existence of directed strongly regular graphs
• Normally regular digraphs, association schemes and related combinatorial structures
• On 4-Cycles and 5-Cycles in Regular Tournaments
• On bipartite graphs of diameter 3 and defect 2
• On Hadamard tournaments
• On spectra of doubly regular asymmetric digraphs of RH-type
• Ordinary graphs and subplane partitions
• Schur rings and non-symmetric association schemes on 64 vertices
• The structure of imprimitive non-symmetric 3-class association schemes
• Two infinite families of failed symmetric designs

Cited in

(13)

• Cayley digraphs with normal adjacency matrices
• Upper bound for the trace norm of the Laplacian matrix of a digraph and normally regular digraphs
• On spectra of doubly regular asymmetric digraphs of RH-type
• Divisible design digraphs and association schemes
• On explicit random-like tournaments
• Some constructions of quasi-strongly regular digraphs
• Minimum arc-cuts of normally regular digraphs and Deza digraphs
• Normally regular digraphs, association schemes and related combinatorial structures
• Classification of regular digraphs, normally regular digraphs, and strongly regular digraphs
• On bipartite graphs of diameter 3 and defect 2
• On the A_-spectrum of joined union of digraphs
• Hoffman's coclique bound for normal regular digraphs, and nonsymmetric association schemes
• On identifying vertices of tournament digraphs

This page was built for publication: Normally regular digraphs

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