×

There is no (75,32,10,16) strongly regular graph. (English) Zbl 1396.05122

Summary: We show that there is no (75, 32, 10, 16) strongly regular graph. The result is obtained by a mix of algebraic and computational approaches. The main idea is to build large enough induced structure and apply the star complement technique. Our result implies that there is no partial geometry \(\operatorname{pg}(4, 7, 2)\) and no regular two-graph with 76 vertices, from which it follows that there also exists no strongly regular graph with parameters (76, 35, 18, 14). In order to solve this classification problem we also develop an efficient algorithm for the problem of finding a maximal clique in a graph.

MSC:

05E30 Association schemes, strongly regular graphs
05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)
05C35 Extremal problems in graph theory
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Azarija, J., Programs related to the paper “on the non existence of a \((75, 32, 10, 16)\) strongly-regular graph”
[2] Azarija, J.; Marc, T., There is no \((95, 40, 12, 20)\) strongly regular graph, (2016), preprint
[3] Behbahani, M.; Lam, C., Strongly regular graphs with non-trivial automorphisms, Discrete Math., 311, 132-144, (2011) · Zbl 1225.05248
[4] Bondarenko, A. V.; Prymak, A.; Radchenko, D., Non-existence of \((76, 30, 8, 14)\) strongly regular graph and some structural tools, (2014), preprint
[5] Brouwer, A. E., Parameters of strongly regular graphs · Zbl 0538.05024
[6] Brouwer, A. E.; van Lint, J. H., Strongly regular graphs and partial geometries, (Enumeration and Design, Waterloo, Ont., 1982, (1984)), 85-122 · Zbl 0555.05016
[7] Cvetković, D. M.; Rowlinson, P.; Simic, S., Eigenspaces of graphs, vol. 66, (1997), Cambridge University Press · Zbl 0878.05057
[8] Degraer, J., Isomorph-free exhaustive generation algorithms for association schemes, (2007), Ghent University, PhD thesis
[9] Godsil, C.; Royle, G. F., Algebraic graph theory, vol. 207, (2013), Springer Science & Business Media
[10] Haemers, W. H., Interlacing eigenvalues and graphs, Linear Algebra Appl., 226, 593-616, (1995) · Zbl 0831.05044
[11] Haemers, W. H.; Tonchev, V. D., Spreads in strongly regular graphs, Des. Codes Cryptogr., 8, 145-157, (1996) · Zbl 0870.05078
[12] Kaski, P.; Junttila, T. A., Engineering an efficient canonical labeling tool for large and sparse graphs, (ALENEX, vol. 7, (2007)), 135-149 · Zbl 1428.68222
[13] Konc, J.; Janezič, D., An improved branch and bound algorithm for the maximum clique problem, MATCH Commun. Math. Comput. Chem., 58, 569-590, (2007) · Zbl 1274.05452
[14] Makhnev, A. A., On strongly regular graphs with parameters \((75, 32, 10, 16)\) and \((95, 40, 12, 20)\), Fundam. Prikl. Mat., 6, 179-193, (2000) · Zbl 0981.05101
[15] McKay, B. D.; Piperno, A., Practical graph isomorphism, II, J. Symbolic Comput., 60, 94-112, (2014) · Zbl 1394.05079
[16] Milošević, M., An example of using star complements in classifying strongly regular graphs, Filomat, 22, 53-57, (2008) · Zbl 1199.05234
[17] Milošević, M.; Stevanović, D., A spectral proof of the uniqueness of a strongly regular graph with parameters \((81, 20, 1, 6)\), European J. Combin., 30, 957-968, (2009) · Zbl 1207.05225
[18] Niskanen, S.; Östergård, P., Cliquer User’s guide: version 1.0, (2003), Communications Laboratory, Helsinki University of Technology Espoo, Finland, Tech. Rep. T48
[19] Rowlinson, P.; Tayfeh-Rezaie, B., Star complements in regular graphs: old and new results, Linear Algebra Appl., 432, 2230-2242, (2010) · Zbl 1217.05156
[20] Seidel, J. J., Strongly regular graphs, (Surveys in Combinatorics, (1979), Cambridge University Press Cambridge), 157-180 · Zbl 0431.05018
[21] Stein, W. A., Sage mathematics software (version 6.5.0), (2015), The Sage Development Team
[22] Tange, O., GNU parallel - the command-line power tool, USENIX Mag., 36, 42-47, (2011)
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.