×
Abiad, Aida; De Boeck, Maarten; Zeijlemaker, Sjanne

On the existence of small strictly Neumaier graphs. (English) Zbl 1536.05481

Graphs Comb. 40, No. 3, Paper No. 51, 25 p. (2024).
Summary: A Neumaier graph is a non-complete edge-regular graph containing a regular clique. In this work, we prove several results on the existence of small strictly Neumaier graphs. In particular, we present a theoretical proof of the uniqueness of the smallest strictly Neumaier graph with parameters (16, 9, 4; 2, 4), we establish the existence of a strictly Neumaier graph with parameters (25, 12, 5; 2, 5), and we disprove the existence of strictly Neumaier graphs with parameters (25, 16, 9; 3, 5), (28, 18, 11; 4, 7), (33, 24, 17; 6, 9), (35, 2212; 3, 5), (40, 30, 22; 7, 10) and (55, 34, 18; 3, 5). Our proofs use combinatorial techniques and a novel application of integer programming methods.

MSC:

05E30 Association schemes, strongly regular graphs
05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
05B15 Orthogonal arrays, Latin squares, Room squares
90C10 Integer programming

Keywords:

Neumaier graphs; edge-regular graphs; regular cliques; Latin squares; integer linear programming

Software:

Gurobi
Cite Review PDF
Full Text: DOI arXiv
OA License

References:

[1] Abiad, A.; Castryck, W.; De Boeck, M.; Koolen, JH; Zeijlemaker, S., An infinite class of Neumaier graphs and non-existence results, J. Comb. Theory Ser. A, 193, 2023 · Zbl 1498.05293 · doi:10.1016/j.jcta.2022.105684
[2] Abiad, A.; DeBruyn, B.; D’haeseleer, J.; Koolen, JH, Neumaier graphs with few eigenvalues, Des. Codes Cryptogr., 90, 2003-2019, 2022 · Zbl 1504.05304 · doi:10.1007/s10623-021-00856-w
[3] Brouwer, AE; Cohen, AM; Neumaier, A., Distance-Regular Graphs, 1989, Berlin, Heidelberg: Springer-Verlag, Berlin, Heidelberg · Zbl 0747.05073 · doi:10.1007/978-3-642-74341-2
[4] Colbourn, CJ; Colbourn, MJ; Harms, JJ; Rosa, A., A complete census of (10, 3, 2) block designs and of Mendelsohn triple systems of order ten, III: (10, 3, 2) block designs without repeated blocks, Congr. Numer., 37, 211-234, 1983 · Zbl 0549.05008
[5] Colbourn, CJ; Dinitz, JH, Handbook of Combinatorial Designs, 2007, Boca Raton: CRC Press, Boca Raton · Zbl 1101.05001
[6] Evans, R.J.: On regular induced subgraphs of edge-regular graphs. Ph.D. thesis, Queen Mary University of London (2020)
[7] Evans, RJ; Goryainov, S.; Panasenko, D., The smallest strictly Neumaier graph and its generalisations, Electron. J. Comb., 26, 2, P2-29, 2019 · Zbl 1414.05223
[8] Ganter, B.; Gülzow, A.; Mathon, R.; Rosa, A., A complete census of (10, 3, 2) block designs and of Mendelsohn triple systems of order ten, IV: (10, 3, 2) designs with repeated blocks, Mathematische Schriften Kassel, 5, 78, 5, 1978
[9] Goryainov, S.V.: Private communication (2023)
[10] Goryainov, SV; Shalaginov, LV, Cayley-Deza graphs with fewer than 60 vertices, Sibirskie Èlektronnye Matematicheskie Izvestiya [Siberian Electron. Math. Rep.], 11, 268-310, 2014 · Zbl 1326.05061
[11] Greaves, GRW; Koolen, JH, Edge-regular graphs with regular cliques, Eur. J. Comb., 71, 194-201, 2018 · Zbl 1387.05272 · doi:10.1016/j.ejc.2018.04.004
[12] Greaves, GRW; Koolen, JH, Another construction of edge-regular graphs with regular cliques, Discret. Math., 342, 10, 2818-2820, 2019 · Zbl 1417.05249 · doi:10.1016/j.disc.2018.09.032
[13] Gurobi Optimization, LLC: (2023). https://www.gurobi.com
[14] López, N.; Miret, J.; Fernández, C., Non existence of some mixed Moore graphs of diameter 2 using SAT, Discret. Math., 339, 2, 589-596, 2016 · Zbl 1327.05093 · doi:10.1016/j.disc.2015.10.001
[15] Neumaier, A.: Regular cliques in graphs and special 1 1/2-designs. Finite Geometries and Designs. London Math. Soc. Lecture Note Series, vol. 49, pp. 244-259 (1981) · Zbl 0466.05026
[16] de Ruiter, FJCT; Biggs, NL, Applications of integer programming methods to cages, Electron. J. Comb., 22, 4, P4-5, 2015 · Zbl 1329.05152
[17] Soicher, LH, On cliques in edge-regular graphs, J. Algebra, 421, 260-267, 2015 · Zbl 1302.05082 · doi:10.1016/j.jalgebra.2014.08.028
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.