On the existence of graphs of diameter two and defect two

In the context of the degree/diameter problem, the ‘defect’ of a graph represents the difference between the corresponding Moore bound and its order. Thus, a graph with maximum degree dd and diameter two has defect two if its order is n=d2−1n=d2−1. Only four extremal graphs of this type, referred to as (d,2,2)(d,2,2)-graphs, are known at present: two of degree d=3d=3 and one of degree d=4d=4 and 5, respectively. In this paper we prove, by using algebraic and spectral techniques, that for all values of the degree dd within a certain range, (d,2,2)(d,2,2)-graphs do not exist.The enumeration of (d,2,2)(d,2,2)-graphs is equivalent to the search of binary symmetric matrices AA fulfilling that AJn=dJnAJn=dJn and A2+A+(1−d)In=Jn+BA2+A+(1−d)In=Jn+B, where JnJn denotes the all-one matrix and BB is the adjacency matrix of a union of graph cycles. In order to get the factorization of the characteristic polynomial of AA in Q[x]Q[x], we consider the polynomials Fi,d(x)=fi(x2+x+1−d)Fi,d(x)=fi(x2+x+1−d), where fi(x)fi(x) denotes the minimal polynomial of the Gauss period ζi+ζi¯, being ζiζi a primitive iith root of unity. We formulate a conjecture on the irreducibility of Fi,d(x)Fi,d(x) in Q[x]Q[x] and we show that its proof would imply the nonexistence of (d,2,2)(d,2,2)-graphs for any degree d>5d>5.