Nonexistence of Almost Moore Digraphs of Diameter Four

Josep Conde, Joan Gimbert, Josep González, Josep M. Miret, Ramiro Moreno


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$.


Almost Moore digraph; characteristic polynomial; cyclotomic polynomial

Full Text: