A parity obstruction for Neumaier graphs with e = s − 2

A Neumaier graph is a non-complete edge-regular graph containing a regular clique; it is strictly Neumaier if it is not strongly regular. We study the class of Neumaier graphs whose parameters satisfy e = s − 2, where s is the size and e the nexus of the regular clique. We show that this condition forces the complement to decompose into C(s, 2) classes of equal size indexed by the pairs of an s-set, so that the whole class is a two-parameter family indexed by (s, μ) with μ = v − 2k + λ. Analysing the local structure we prove that the number of edges between two classes sharing an index is completely determined by the distribution of a certain perfect matching, and that the resulting integrality conditions give a parity obstruction: if μ is odd then 4 | s. In particular there is no Neumaier graph with parameters (10μ+5, 6μ+4, 3μ+3; 3, 5) for any odd μ. This answers a question of Abiad, De Boeck and Zeijlemaker, who observed computationally that these parameter sets are eliminated with unexpected ease and conjectured an underlying theoretical reason. Combining the obstruction with an exhaustive search for the remaining cases, we eliminate five further parameter sets left open in their table, namely (28, 15, 6; 2, 4), (34, 18, 7; 2, 4), (40, 21, 8; 2, 4), (45, 28, 15; 3, 5) and (46, 24, 9; 2, 4). All evidence is consistent with the conjecture that the unique strictly Neumaier graph on 16 vertices is the only one with e = s − 2. The authors are listed in alphabetical order and contributed equally.