On the structure of digraphs with order close to the Moore bound (Q1393025)

The Moore bound for a diregular digraph of degree \(d\) (that is, the outdegree and indegree is \(d\) for every vertex) and diameter \(k\) is \(M_{d,k}= 1+ d+\cdots+ d^k\). It is known that digraphs of order \(M_{d,k}\) do not exist for \(d>1\) and \(k>1\). Thus it makes sense to consider digraphs of degree \(d\), diameter \(k\), and order \(M_{d,k}- 1\), sometimes called \((d,k)\)-digraphs. Various results are known for specific cases. In this paper, further necessary conditions are presented for the existence of \((d,k)\)-digraphs. In particular, for \(d, k\geq 3\), it is shown that a \((d,k)\)-digraph contains either no cycle of length \(k\) or exactly one cycle of length \(k\).