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

directed graphsassociation schemesdesign theory

Mathematics Subject Classification ID

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

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.

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

• 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?)
• A Family of Difference Sets
• A directed graph version of strongly regular graphs
• 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
• 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 Hadamard tournaments
• On bipartite graphs of diameter 3 and defect 2
• 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

(11)

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

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)