Skip to content
DraconiticResearch
Search Sources API
203,203 studies31 sourcesUpdated 12 min ago
PreprintCC BY 4.0arXiv

A unified framework for existing and new constructions of Neumaier graphs

  • Aida Abiad
  • Wouter Castryck
  • Maarten De Boeck
  • Antonina Khramova
  • Thijs van Veluw
Open at sourcePDFDOICite

Abstract

A Neumaier graph is a non-complete edge-regular graph containing a regular clique; it is called strictly Neumaier if it is not strongly regular. In this paper we present a construction using finite rings that unifies several known results and yields three new families, each containing infinitely many strictly Neumaier graphs. We characterize when the resulting graphs are strongly regular. The family obtained from norm functions of finite field extensions includes the collinearity graphs of generalized quadrangles of *-Tits type arising from the classical hyperoval. We further show that, when the cyclotomic numbers involved have order at most seven, four types of rings suffice to obtain, up to isomorphism, all strictly Neumaier graphs arising from our construction. As a consequence of our results, each of these four types has now been used to construct Neumaier graphs.

Related

  1. Neumaier graphs of coherent rank five
    Gary Greaves, Zhao Kuang Tan
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv
  2. Change detection with conformal martingales: new optimal constructions, and suboptimality of existing methods
    Swapnaneel Bhattacharyya, Aaditya Ramdas
    arXivPreprintarXiv licenceFull textStatisticsarXiv
  3. Binary Multiple-Node-Erasure-Correcting Codes over Complete Graphs: Constructions, q-Ary Metric Balls, and Duality
    Aryeh Lev Zabokritskiy
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  4. Bipartite edge frustration of nut graphs: proofs and constructions
    Nino Bašić, Patrick W. Fowler
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  5. Concatenation trees: A framework for efficient universal cycle and de Bruijn sequence constructions
    Joe Sawada, Jackson Sears, A. Trautrim +1
    Discrete Applied MathematicsPeer-reviewedLicence not statedFull text6 citedCombinatorics & discrete mathematicsOpenAlex

Cite

BibTeXRIS
BibTeX
@misc{abiad2026unified,
  title = {{A unified framework for existing and new constructions of Neumaier graphs}},
  author = {Aida Abiad and Wouter Castryck and Maarten De Boeck and Antonina Khramova and Thijs van Veluw},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2610.01273},
  eprint = {2610.01273},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.01273},
  note = {CC BY 4.0},
}
RIS
TY  - UNPB
TI  - A unified framework for existing and new constructions of Neumaier graphs
AU  - Aida Abiad
AU  - Wouter Castryck
AU  - Maarten De Boeck
AU  - Antonina Khramova
AU  - Thijs van Veluw
PY  - 2026
DA  - 2026/10/01
PB  - arXiv
DO  - 10.48550/arxiv.2610.01273
UR  - https://arxiv.org/abs/2610.01273
AB  - A Neumaier graph is a non-complete edge-regular graph containing a regular clique; it is called strictly Neumaier if it is not strongly regular. In this paper we present a construction using finite rings that unifies several known results and yields three new families, each containing infinitely many strictly Neumaier graphs. We characterize when the resulting graphs are strongly regular. The family obtained from norm functions of finite field extensions includes the collinearity graphs of generalized quadrangles of *-Tits type arising from the classical hyperoval. We further show that, when the cyclotomic numbers involved have order at most seven, four types of rings suffice to obtain, up to isomorphism, all strictly Neumaier graphs arising from our construction. As a consequence of our results, each of these four types has now been used to construct Neumaier graphs.
ER  -