Further Results on Almost Moore Digraphs

Abstract

The nonexistence of digraphs with order equal to the Moore bound ${\mathrm{M}}_{\mathrm{d},\mathrm{k}}=1+d+\dots +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}}_{\mathrm{d},\mathrm{k}}–1$, degree $d$, diameter $k$ ($d,k\ge 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\ge 1$. As a consequence, for diameter $k=2$ and degree $d$, $2\le d\le 12$, we show that there are no almost Moore digraphs of order ${\mathrm{M}}_{\mathrm{d},2}–1$ with one vertex in a $2$-cycle $C_2$ except the digraphs with every vertex in $C_2$.