## Nonexistence of almost Moore digraphs of diameter three

### Summary

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

### Keywords/Phrases

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