Neumaier graphs

New constructions and properties


Contents



Introduction


In the early 1980s, Neumaier [N81] studied regular cliques in edge-regular graphs, and a certain class of designs whose point graphs are strongly regular and contain regular cliques. In his article, he asked if there exists an edge-regular, non-strongly regular graph which contains regular clique.

Almost 40 years later, Greaves and Koolen finally proved that such graphs exist, and give two general constructions of graphs [GK18a; GK18b].

Motivated by Neumaier’s study of edge-regular graphs with regular cliques, we introduce the following definitions.

Neumaier graph
A non-complete edge-regular graph containing a regular clique.
Strictly Neumaier graph
A non-strongly regular Neumaier graph.

After the first constructions of strictly Neumaier graphs were published, there has been an increased interest the study of these graphs (see References for some related articles).

Constructions


All currently known constructions (as of 21/10/2024) are found in the following articles.

  • In [GK18a] the authors prove that strictly Neumaier graphs exist, and construct an infinite family of strictly Neumaier graphs.
  • In [GK18a] the authors give a construction of strictly Neumaier graphs that uses antipodal classes in distance-regular graphs.
  • In [EG19] the authors find the smallest strictly Neumaier graph. Further, for each positive integer \(i\) they construct a strictly Neumaier graphs containing regular cliques of nexus \(2^i\).
  • In (missing reference), the authors present a construction of Neumaier graphs containing regular cliques with nexus \(1\). This construction generalises the two constructions of Neumaier graphs found in [GK18a] and [GK18b].
  • In [ACD+23], number theoretical arguments are used to construct infinitely many strictly Neuamier graphs using the construction from (missing reference).

These constructions make use of tools from algebraic graph theory, finite geometry and number theory. Each new construction can give a connection to another area of mathematics, and help us gain a better understanding of these graphs. This gives continued motivation for constructing strictly Neumaier graphs, whether it be the construction of infinite families or the discovery sporadic examples.


Properties


Now that several constructions of strictly Neumaier graphs have been observed, interest in the possible algebraic and combinatorial properties of Neumaier graphs has emerged.

For example, basic parameter restrictions can be found in [EG19], and further restrictions were found and used to prove nonexistence results in [ACD+23]. The eigenvalues of a Neumaier graph have been studied in [ADD+21], where it is proved that a Neumaier graph cannot have exactly 4 distinct eigenvalues.

As this class of graphs have not been deeply studied, their are many questions about their possible structure.

  • Classification of Neumaier graphs with extremal parameters and parameter restrictions have already been found, and is still an area to be explored.
  • The spectrum of Neumaier graphs are less restricted than strongly regular graphs, but seem to have more structure than edge-regular graphs in general.
  • Neumaier’s original question of existence was motivated by transitivity conditions he observed in strongly regular graphs, so it is natural to also study other transitivity conditions in Neumaier graphs.


An open problem


Currently, all known strictly Neumaier graph contain regular cliques with nexus \(2^i\), for a non-negative integer \(i\). Therefore, one of the major open problems in this area is the following:

For every integer \(m>0\), does there exist a strictly Neumaier graph containing an \(m\)-regular clique?

As the definition of Neumaier graphs seems less restrictive than that of strongly regular graphs, it is believed that the answer to this problem is ‘yes’. The discovery of any sporadic examples or infinite families of strictly Neumaier graphs having regular cliques with nexus not \(2^i\) will be a significant step towards solving this problem.


Small strictly Neumaier graphs


Below is a table containing information about the smallest known strictly Neumaier graphs (as of 21/10/2024). The content of each column is as follows.

Parameters
All parameter tuples \((v,k,\lambda;m,s)\) of the known strictly Neumaier graphs on at most \(310\) vertices.
Description
A short note on the known strictly Neumaier graphs with the corresponding parameters.
Downloads
Files containing some of the known strictly Neumaier graphs with the corresponding parameters. The ‘gap’ files contain a list of graphs in GRAPE format in GAP (see [GRAPE; GAP]). The ‘mat’ files contain adjacency matrices of the same graphs. The number in brackets denotes how many graphs are currently stored in the files.


Parameters Description Downloads (#graphs)
(16, 9, 4; 2, 4) Unique smallest, vertex-transitive [EG19] gap, mat (1)
(24, 8, 2; 1, 4) 4 vertex-transitive, 1 diameter 3 (missing reference) gap, mat (6)
(28, 9, 2; 1, 4) 2 vertex-transitive, [GK18a] gap, mat (4)
(40, 12, 2; 1, 4) 1 vertex-transitive, (missing reference) gap, mat (1)
(52, 15, 2; 1, 4) 1 vertex-transitive, [GK18a] NA (1)
(64, 35, 18; 4, 8) [EG19] NA (>2)
(65, 16, 3; 1, 5) 1 vertex-transitive, (missing reference) gap, mat (1)
(78, 17, 4; 1, 6) 8 vertex-transitive, (missing reference) gap, mat (8)
(168, 27, 6; 1, 8) 1 vertex-transitive, (missing reference) NA (12)
(185, 40, 3; 1, 5) 1 vertex-transitive, [ACD+23] NA (1)
(250, 33, 8; 1, 10) 1 vertex-transitive, (missing reference) NA (16)
(256, 135, 70; 8, 16) [EG19] NA (>2)
(310, 39, 8; 1, 10) 1 vertex-transitive, (missing reference) gap, mat (1)


References

2023

  1. DM
    A general construction of strictly Neumaier graphs and a related switching
    Rhys J. EvansSergey GoryainovElena V. Konstantinova, and 1 more author
    Discrete Mathematics, 2023
  2. An infinite class of Neumaier graphs and non-existence results
    Aida AbiadWouter CastryckMaarten De Boeck, and 2 more authors
    Journal of Combinatorial Theory, Series A, 2023

2022

  1. GAP
    GAP – Groups, Algorithms, and Programming, Version 4.12.2
    2022

2021

  1. DCC
    Neumaier graphs with few eigenvalues
    Designs, Codes and Cryptography, 2021

2019

  1. The smallest strictly Neumaier graph and its generalisations
    Rhys J. EvansSergey Goryainov, and Dmitry Panasenko
    Electronic Journal of Combinatorics, 2019

2018

  1. GAP
    GRAPE, GRaph Algorithms using PErmutation groups, Version 4.8
    2018
    Refereed GAP package
  2. DM
    Another construction of edge-regular graphs with regular cliques
    Discrete Mathematics, 2018
  3. EJC
    Edge-regular graphs with regular cliques
    European Journal of Combinatorics, 2018

1981

  1. LMS
    Regular cliques in graphs and special 1 1⁄2 designs
    In Finite Geometries and Designs: Proceedings of the Second Isle of Thorns Conference 1980, 1981