On diregular digraphs with degree two and excess two

Abstract

An important topic in the design of efficient networks is the construction of $(d,k,+\epsilon )$-digraphs, i.e. $k$-geodetic digraphs with minimum out-degree $\ge d$ and order $M(d,k)+\epsilon$, where $M(d,k)$ represents the Moore bound for degree $d$ and diameter $k$ and $\epsilon >0$ is the (small) excess of the digraph. Previous work has shown that there are no $(2,k,+1)$-digraphs for $k\ge 2$. In a separate paper, the present author has shown that any $(2,k,+2)$-digraph must be diregular for $k\ge 2$. In the present work, this analysis is completed by proving the nonexistence of diregular $(2,k,+2)$-digraphs for $k\ge 3$ and classifying diregular $(2,2,+2)$-digraphs up to isomorphism.

arXiv commentUpdated to reflect referees' comments