Nonexistence of Almost Moore Digraphs of Diameter Three - Conde, J.; Gimbert, J.; Gonzàlez, J.; Miret, J. M.; Moreno, R. (The Electronic Journal of Combinatorics, 2008)
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+… +d^k, 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. The enumeration of almost Moore digraphs of degree d and diameter k=3 turns out to be equivalent to the search of binary matrices A fulfilling that AJ=dJ and I+A+A^2+A^3=J+P, where J denotes the all-one matrix and P is a permutation matrix. We use spectral techniques in order to show that such equation has no (0,1)-matrix solutions. More precisely, we obtain the factorization in Q[x] of the characteristic polynomial of A, in terms of the cycle structure of P, we compute the trace of A and we derive a contradiction on some algebraic multiplicities of the eigenvalues of A. In order to get the factorization of (xI-A) we determine when the polynomials F_n(x)=Φ_n(1+x+x^2+x^3) are irreducible in Q[x], where Φ_n(x) denotes the n-th cyclotomic polynomial, since in such case they become ’big pieces’ of (xI-A). By using concepts and techniques from algebraic number theory, we prove that F_n(x) is always irreducible in Q[x], unless n=1,10. So, by combining tools from matrix and number theory we have been able to solve a problem of graph theory.