Conde, J.; Gimbert, J.; Gonzalez, J.; Miret, J.M.; Moreno, R.

Nonexistence of almost Moore digraphs of diameter three

Electron. J. Comb. 15(1), Research Paper R87, 14 p. (2008)


Summary: Almost Moore digraphs appear in the context of the degree/diameter problem as a class of extremal directed graphs, in the sense that their order is one less than the unattainable Moore bound M (d, k) = $1 + d + \cdot \cdot \cdot + dk$, where d > 1 and k > 1 denote the maximum out-degree and diameter, respectively. So far, the problem of their existence has only been solved when d = 2, 3 or k = 2. In this paper, we prove that almost Moore digraphs of diameter k = 3 do not exist for any degree d.

Mathematics Subject Classification

05C20, 05C50, 11R18


almost Moore digraph, characteristic polynomial, cyclotomic polynomial, permutation cycle structure, trace