Further Results on Almost Moore Digraphs

The nonexistence of digraphs with order equal to the Moore bound \(\mathrm{M_{d,k}} = 1+d+\ldots+ d^h\) for \(d,k > 1\) has led to the study of the problem of the existence of “almost” Moore digraphs, namely digraphs with order close to the Moore bound. In [1], it was shown that almost Moore digraphs of order \(\mathrm{M_{d,k}} – 1\), degree \(d\), diameter \(k\) (\(d, k \geq 3\)) contain either no cycle of length \(k\) or exactly one such cycle. In this paper, we shall derive some further necessary conditions for the existence of almost Moore digraphs for degree \(d\) and diameter \(k \geq 1\). As a consequence, for diameter \(k = 2\) and degree \(d\), \(2 \leq d \leq 12\), we show that there are no almost Moore digraphs of order \(\mathrm{M_{d,2}} – 1\) with one vertex in a \(2\)-cycle \(C_2\) except the digraphs with every vertex in \(C_2\).