Further results on almost Moore digraphs.
Edy Tri Baskoro, Mirka Miller, Ján Plesnı́k · 2000
The nonexistence of digraphs with order equal to the Moore bound Md;k = 1+d+: : :+d k for d; k ? 1 has lead 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 Md;k \\Gamma 1, degree d, diameter k (d; k 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 and diameter greater than 1. As a consequence, for diameter 2 and degree d, 2 d 12, we show that there are no almost Moore digraphs of order M d;2 \\Gamma 1 with one vertex in a C2 except the digraphs with every vertex in C2.