Nonexistence of Almost Moore Digraphs of Diameter Four

  • Josep Conde
  • Joan Gimbert
  • Josep González
  • Josep M. Miret
  • Ramiro Moreno
Keywords: Almost Moore digraph, characteristic polynomial, cyclotomic polynomial

Abstract

Regular digraphs of degree $d>1$, diameter $k>1$ and order $N(d,k) = d+\cdots +d^k$ will be called almost Moore $(d,k)$-digraphs. So far, the problem of their existence has only been solved when $d=2, 3$ or $k = 2, 3$. In this paper we prove that almost Moore digraphs of diameter 4 do not exist for any degree $d$.

Published
2013-03-31
Article Number
P75