On the existence of graphs of diameter two and defect two (Q1025938)

A \((d,2,2)\)-graph is a \(n\)-vertex graph of maximum degree \(d\) and diameter 2 for which \(n=d^2-1\). Only 4 such graphs are known, two with \(d=3\) and one for \(d=4,5\) each. It is shown that irreducibility in \(\mathbb{Q}[x]\) of the characteristic polynomial of certain binary symmetric matrices depending on \(d>5\) implies nonexistence of a \((d,2,2)\)-graph, and such irreducibility is conjectured to always hold. Using the mathematics software PARI the conjecture has been verified for all \(d=6,\ldots,50\).