On the nonexistence of almost Moore digraphs

Digraphs of maximum out-degree at most d > 1, diameter at most k > 1 and order N(d, k) = d + ... + d(k) are called almost Moore or (d, k)-digraphs. So far, the problem of their existence has been solved only when d = 2, 3 or k = 2, 3, 4. In this paper we derive the nonexistence of (d, k)-digraphs, with k > 4 and d > 3, under the assumption of a conjecture related to the factorization of the polynomials Phi(n)(1 + x + ... + x(k)), where Phi(n)(x) denotes the nth cyclotomic polynomial and 1 < n <= N(d, k). Moreover, we prove that almost Moore digraphs do not exist for the particular cases when k = 5 and d = 4, 5 or 6. (C) 2014 Elsevier Ltd. All rights reserved