For odd prime-power q greater than 3, only four exceptional graph constructions beyond the tangency family meet the Deza condition in the analyzed scheme, an arXiv preprint reports. They are the secant relation at q=9 for both signs of the quadric, the tangent-plus-secant union at q=5 for the minus sign, and the tangent-plus-external union at q=7 for the plus sign.
Here, the Deza condition means that a graph’s pairs of vertices have no more than two possible numbers of common neighbors. The paper’s classification checks this through the quantities c1(S), c2(S) and c3(S), which count common neighbors for pairs in the three relation classes.
The geometry behind the test
The construction starts with one fixed class of points called anisotropic on a non-degenerate quadric Qε(3,q) in PG(3,q), a projective space over a finite field. Lines joining pairs of those points are classified as tangent, secant or external, forming a symmetric three-class association scheme.
To test each non-empty proper union of the relations, the author substitutes the scheme’s intersection numbers into c1(S), c2(S) and c3(S), then solves for cases in which at least two values coincide. Those are the cases that pass the Deza criterion.
The tangency graph, S={1}, is the family that works for every allowed q and either sign. For it, two relation types have 2(q−1) common neighbors and the remaining type has 2(q+1): the outlier is c3 when ε=+ and c2 when ε=−. The paper says the graph is not strongly regular for q>3.
Four precise exceptions
All four exceptional graphs are strictly Deza. In the Q+(3,9) secant case, the graph has 360 vertices, degree 135, and common-neighbor values 45 and 54. The Q−(3,9) secant case has 369 vertices, degree 108, and values 27 and 36. The Q−(3,5) tangent-plus-secant case has 65 vertices, degree 34, and values 15 and 18. The Q+(3,7) tangent-plus-external case has 168 vertices, degree 111, and values 70 and 75.
The reported a- and b-children are the relation graphs associated with the two common-neighbor values. In that same order, the child pairs are (R3, R1∪R2), (R1∪R2, R3), (R2, R1∪R3), and (R3, R1∪R2), with each pair ordered as (a-child, b-child). None of the reported children is strongly regular.
Explicit spectra are also reported for all four graphs. The paper says it obtained them through simultaneous diagonalization in the Bose–Mesner algebra, specialization of the scheme’s eigenmatrix, and summation over the included relations. Because the supplied spectrum notation is flattened by text extraction, detailed eigenvalue-multiplicity readings may require checking against the typeset source.
From line relations to named graphs
The preprint gives the exceptional graphs several structural identities. The Q+(3,7) graph is described as a Cayley graph on PSL(2,7), a graph built from a group and a chosen connection set; the Q+(3,9) graph is Cay(A6, 2A∪4A). The Q−(3,9) graph is described as a disjointness graph on either of two PSL(2,81) orbits on Baer sublines of PG(1,81).
In the 65-vertex elliptic case, the manuscript identifies R2, of valency 10, with the Doro-Hall graph, identifies R3 as its distance-2 graph, and states that the two children are the Doro-Hall graph and its complement. The extracted text also contains an apparent degree/isomorphism inconsistency in this subsection, so these named identifications need checking against the typeset source.
A result with a defined boundary
The result is conditional on the stated setting: one fixed class of anisotropic points on a non-degenerate Qε(3,q) in PG(3,q), odd prime-power q>3, and non-empty proper relation unions. It should not be read as a classification of all quadric-based relation unions.
Among the odd-dimensional hyperbolic and elliptic quadrics discussed, the tangency Deza property occurs only in projective dimension 3. Classifying all relation unions for odd n>3 is left as an explicit open problem.
The manuscript is listed as arXiv:2608.20064v1 and dated 20 Aug 2026; no journal publication is reported in the supplied metadata.
Paper data and sources
Original title: Classification of Deza graphs from anisotropic association schemes of quadrics
Authors: Valentino Smaldore
Journal/Repository: arXiv
Status: Preprint, not yet peer-reviewed
First online: 2026-08-20
DOI: Not available
Original paper · Full text