Vertex-transitive Neumaier graphs

Document Type : Research Paper

Author

Department of Mathematics, Shahid Chamran University of Ahvaz, Ahvaz, Iran

Abstract

A graph $\Gamma$ is called edge-regular whenever it is regular and for any two adjacent vertices, the number of their common neighbors is independent of the choice of vertices. A clique $C$ in $\Gamma$ is called regular whenever for any vertex out of $C$, the number of its neighbors in $C$ is independent of the vertex. A Neumaier graph is a non-complete edge-regular graph with a regular clique. In this paper, we study vertex-transitive Neumaier graphs. We give a necessary and sufficient condition under which a vertex-transitive Neumaier graph is strongly regular. We also identify Neumaier Cayley graphs with small valency at most $10$ among vertex-transitive Neumaier graphs.

Keywords

Main Subjects

References

[1] A. Abdollahi, E. R. van Dam and M. Jazaeri, Distance-regular Cayley graphs with least eigenvalue −2, Des. Codes Cryptogr., 84 no. 1-2 (2017) 73–85.
[2] A. Abdollahi and M. Jazaeri, On groups admitting no integral Cayley graphs besides complete multipartite graphs, Appl. Anal. Discrete Math., 7 no. 1 (2013) 119–128.
[3] A. Abiad, W. Castryck, M. De Boeck, J. H. Koolen and S. Zeijlemaker, An infinite class of Neumaier graphs and non-existence results, J. Combin. Theory Ser. A, 193 (2023) 30 pp.
[4] A. Abiad, B. De Bruyn, J. D’haeseleer and J. H. Koolen, Neumaier graphs with few eigenvalues, Des. Codes Cryptogr., 90 no. 9 (2022) 2003–2019.
[5] A. Abiad, M. De Boeck and S. Zeijlemaker, On the existence of small strictly Neumaier graphs, Graphs Combin., 40 no. 3 (2024) 25 pp.
[6] A. E. Brouwer, A. M. Cohen and A. Neumaier, Distance-regular graphs, Springer-Verlag, Berlin, 1989.
[7] A. E. Brouwer and W. H. Haemers, Spectra of graphs, Universitext, Springer, New York, 2012.
[8] A. E. Brouwer and H. van Maldeghem, Strongly regular graphs, Cambridge University Press, Cambridge, 2022.
[9] E. R. van Dam and M. Jazaeri, Distance-regular Cayley graphs with small valency, Ars Math. Contemp., 17 (2019) 203–222.
[10] R. J. Evans, AGT, Algebraic graph theory, Version 0.3.1 (2022). https://gap-packages.github.io/agt/.
[11] R. J. Evans, On regular induced subgraphs of edge-regular graphs, Queen Mary University of London, (2020).
[12] R. J. Evans, S. Goryainov and D. Panasenko, The smallest strictly Neumaier graph and its generalisations, Electron. J. Combin., 26 no. 2 (2019) 30 pp.
[13] C. Godsil and G. Royle, Algebraic graph theory, Springer-Verlag, New York, 2001.
[14] G. R. W. Greaves and J. H. Koolen, Edge-regular graphs with regular cliques, European J. Combin., 71 (2018) 194–201.
[15] A. Neumaier, Regular cliques in graphs and special 1 21 -designs, Finite geometries and designs (Proc. Conf., Chelwood Gate, 1980), London Math. Soc. Lecture Note Ser., 49, Cambridge Univ. Press, Cambridge-New York, (1981) 244–259.
[16] L. H. Soicher, On cliques in edge-regular graphs, J. Algebra, 421 (2015) 260–267.
[17] L. H. Soicher, GRAPE, GRaph Algorithms using PErmutation groups, Version 4.9.0 (2022), https://gap-packages.github.io/grape.
[18] The GAP Group, GAP – Groups, Algorithms, and Programming, Version 4.12.1 (2023), http://www.gap-system.org.
Transactions on Combinatorics
Volume 15, Issue 3 - Serial Number 3
September 2026
Pages 203-214

Files

History

  • Receive Date: 14 January 2025
  • Revise Date: 03 October 2025
  • Accept Date: 04 October 2025
  • Published Online: 31 October 2025

Share

How to cite

Statistics