Diregularity of digraphs of out-degree three and order two less than Moore bound

Abstract

It is easy to show that any digraph with out-degree at most $d \ge 2$, diameter $k \ge 2$ and order $n=d+d^2+\dots + d^k - 1$, that is, two less than Moore bound must have all vertices of out-degree $d$. In other words, the out-degree of the digraph is constant $(=d)$. However, establishing the diregularity or otherwise of the in-degree of such a digraph is not easy. It was proved that every digraph of out-degree at most two, diameter $k \ge 3$ and order two less than the Moore bound is diregular \cite{SM00}. In this paper, we consider the diregularity of digraphs of out-degree at most three, diameter $k \ge 3$ and order two less than the Moore bound.