Neumaier graphs
Constructions, nexus values and open problems
Literature reviewed: 17 October 2026.
Contents
Introduction
In 1981, Neumaier [N81] studied regular cliques in edge-regular graphs and asked whether an edge-regular graph containing a regular clique must be strongly regular. Greaves and Koolen answered this question negatively by constructing graphs with a regular clique that are edge-regular but not strongly regular [GK18a; GK19].
- Neumaier graph
- A non-complete edge-regular graph containing a regular clique.
- Strictly Neumaier graph
- A Neumaier graph that is not strongly regular.
A regular clique has nexus \(e\) if every vertex outside the clique has exactly \(e\) neighbours in it. We write the parameters of a Neumaier graph as \((v,k,\lambda;e,s)\): the graph has \(v\) vertices and valency \(k\), adjacent vertices have \(\lambda\) common neighbours, and it contains an \(e\)-regular clique of size \(s\).
Since the first constructions, strictly Neumaier graphs have provided examples connecting algebraic graph theory, finite geometry, number theory and computation. Recent work has substantially expanded both the known constructions and the range of possible nexuses.
Constructions
Greaves and Koolen gave the first infinite family of strictly Neumaier graphs [GK18a], followed by a construction using antipodal classes in distance-regular graphs [GK19].
Evans, Goryainov, Konstantinova and Mednykh developed a general construction with nexus one and a related switching operation [EGKM23]. Abiad, Castryck, De Boeck, Koolen and Zeijlemaker combined this construction with number-theoretic arguments involving Jacobi sums to obtain further infinite families [ACD+23].
More recently, Abiad, Castryck, De Boeck, Khramova and van Veluw have developed a finite-ring framework that unifies several earlier constructions [ACCKV26]. It yields three new families, based on finite-field norm maps, dual numbers over \(\mathbb F_4\), and quotients of the Eisenstein integers. Each contains infinitely many strictly Neumaier graphs with nexus one.
Constructions with power-of-two nexus began with Evans, Goryainov and Panasenko, who determined the unique smallest strictly Neumaier graph, with parameters \((16,9,4;2,4)\), and constructed two infinite sequences with nexus \(2^i\) for every positive integer \(i\) [EG19]. Evans, Goryainov, Ryabov and Zhao subsequently used relative difference sets to construct an infinite family of strictly Neumaier Cayley graphs with nexus \(2^i\) for every positive even integer \(i\) [EGRZ27]. Their work also gives a criterion and an algorithm for constructing Neumaier Cayley graphs whose regular cliques form a spread of subgroup cosets.
The known nexuses are no longer restricted to powers of two. The small-graph study of Abiad, De Boeck and Zeijlemaker already reports examples with parameters \((64,28,12;3,8)\) and \((64,42,26;5,8)\), crediting computations communicated by Goryainov in 2023 [ADZ24]. These examples also occur in the subsequent Cayley enumeration [EGRZ27].
Greaves and Tan’s construction using cyclotomy over products of finite fields provides strictly Neumaier examples with every nexus \(e\in\{1,2,\ldots,20\}\), as well as further values [GT26a]. The construction also contains strongly regular graphs, so its strictness conditions matter when choosing examples. It settles many individual cases of the general existence question, but does not settle it for arbitrary nexus.
Greaves and Tan have also constructed an infinite family of strictly Neumaier graphs of coherent rank five [GT26b]. For every prime power \(q\geq7\) with \(q\equiv3\pmod4\), their construction gives parameters
\[\left( (q+1)q(q-2),\; \frac{(q+1)^2(q-2)}{2},\; \frac{(q+1)(q^2+q-8)}{4};\; \frac{(q-1)^2}{2},\; q(q-2) \right).\]In particular, the nexus is
\[e=\frac{(q-1)^2}{2}.\]The choices \(q=7,11,19,23,27\) give nexuses \(18,50,162,242,338\), respectively. This supplies infinitely many strictly Neumaier graphs whose nexus is not a power of two. The smallest member of this family has parameters \((280,160,96;18,35)\). The construction uses Hadamard matrices and mutually appropriate Latin squares; its graphs also have exactly five distinct adjacency eigenvalues.
Properties
Small graphs and parameter restrictions
Basic parameter restrictions appear in [EG19], with further nonexistence results in [ACD+23]. Abiad, De Boeck and Zeijlemaker give a theoretical proof of the uniqueness of the 16-vertex example, construct a graph with parameters \((25,12,5;2,5)\) from a Latin square, and use integer programming to exclude several other parameter sets [ADZ24]. Such exclusions concern particular parameter sets, rather than ruling out a nexus at every order.
Eigenvalues and coherent rank
Abiad, De Bruyn, D’haeseleer and Koolen proved that a Neumaier graph cannot have exactly four distinct eigenvalues [ADD+22]. Examples with exactly five eigenvalues are now known: De Bruyn, Evans, Goryainov and Koolen construct 1063 pairwise nonisomorphic graphs with parameters \((48,14,2;1,4)\), of which 25 have exactly five eigenvalues [DBEGK26]. Their graph6 data is available separately.
Coherent rank measures the dimension of a graph’s coherent closure. The family described above establishes the existence of strictly Neumaier graphs of coherent rank five [GT26b]. Questions remain about the smallest possible order at this rank and the structure of the coherent closure.
Smallest eigenvalue and colourings
Yang and Koolen prove that only finitely many strictly Neumaier graphs have smallest eigenvalue at least \(-3\) [YK25]. Abiad, De Bruyn and van Veluw show that a Hoffman-colourable Neumaier graph must be strongly regular; consequently, strictly Neumaier graphs are not Hoffman colourable [ADBV26].
An open problem
Although examples are known for every nexus from 1 to 20 and for further unbounded sequences of values, the general existence question remains [GT26a; EGRZ27]:
For every positive integer \(e\), does there exist a strictly Neumaier graph containing an \(e\)-regular clique?
The new families show that nexuses need not be powers of two. The remaining challenge is to obtain a strictly Neumaier graph for an arbitrary prescribed positive nexus. An infinite sequence of realized nexuses does not by itself answer this question.
Small strictly Neumaier graphs
The following table lists strictly Neumaier graphs on at most 310 vertices. The Cayley counts refer to graphs admitting a spread of subgroup cosets [EGRZ27].
The GAP files contain lists of graphs in GRAPE format, and the matrix files contain adjacency matrices of the same graphs [GRAPE; GAP]. Numbers in the Downloads column count graphs in the linked collection. A dash means that no download is linked here.
| Parameters | Description | Downloads (#graphs) |
|---|---|---|
| (16, 9, 4; 2, 4) | Unique smallest, vertex-transitive [EG19; ADZ24] | gap, mat (1) |
| (24, 8, 2; 1, 4) | Four vertex-transitive examples; a diameter-three example is also known [GK19; EGKM23] | gap, mat (6) |
| (25, 12, 5; 2, 5) | A Latin-square construction [ADZ24] | — |
| (28, 9, 2; 1, 4) | Two vertex-transitive examples [GK18a] | gap, mat (4) |
| (40, 12, 2; 1, 4) | A vertex-transitive example [EGKM23] | gap, mat (1) |
| (48, 14, 2; 1, 4) | A construction gives 1063 examples, including 25 with five eigenvalues [DBEGK26] | graph6 collection (1063) |
| (52, 15, 2; 1, 4) | A vertex-transitive example [GK18a] | — |
| (60, 14, 4; 1, 6) | An example from the antipodal construction [GK19; ADZ24] | — |
| (64, 28, 12; 3, 8) | 18 Cayley examples with a subgroup-coset spread [EGRZ27] | — |
| (64, 35, 18; 4, 8) | 1380 Cayley examples with a subgroup-coset spread [EGRZ27] | — |
| (64, 42, 26; 5, 8) | A Cayley example with a subgroup-coset spread [EGRZ27] | — |
| (65, 16, 3; 1, 5) | A vertex-transitive example [EGKM23; ACD+23] | gap, mat (1) |
| (78, 17, 4; 1, 6) | Eight vertex-transitive examples [EGKM23] | gap, mat (8) |
| (112, 36, 10; 2, 7) | A cyclotomic construction with coherent rank six [GT26a] | — |
| (133, 42, 13; 2, 7) | A cyclotomic construction with coherent rank six [GT26a] | — |
| (168, 27, 6; 1, 8) | Twelve reported examples, including one vertex-transitive [EGKM23] | — |
| (185, 40, 3; 1, 5) | A vertex-transitive example [ACD+23] | — |
| (208, 72, 26; 4, 13) | A cyclotomic construction with coherent rank six [GT26a] | — |
| (232, 35, 6; 1, 8) | A cyclotomic construction [GT26a] | — |
| (243, 34, 7; 1, 9) | A norm-map construction [ACCKV26] | — |
| (250, 33, 8; 1, 10) | Sixteen reported examples, including one vertex-transitive [EGKM23] | — |
| (256, 135, 70; 8, 16) | Examples from the power-of-two families [EG19] | — |
| (280, 160, 96; 18, 35) | Coherent rank five and five distinct eigenvalues [GT26b] | — |
| (310, 39, 8; 1, 10) | A vertex-transitive example [EGKM23] | gap, mat (1) |