ALGEBRAIC COMBINATORICS

no. 5
On highly regular strongly regular graphs
Pech, Christian1
1 Radebeul, Germany
Algebraic Combinatorics, Volume 4 (2021) no. 5, pp. 843-878.

In this paper we unify several existing regularity conditions for graphs, including strong regularity, k-isoregularity, and the t-vertex condition. We develop an algebraic composition/decomposition theory of regularity conditions. Using our theoretical results we show that a family of non rank 3 graphs known to satisfy the 7-vertex condition fulfills an even stronger condition, (3,7)-regularity (the notion is defined in the text). Derived from this family we obtain a new infinite family of non rank 3 strongly regular graphs satisfying the 6-vertex condition. This strengthens and generalizes previous results by Reichard.

Received:
Revised:
Accepted:
Published online:
DOI: 10.5802/alco.183
Classification: 05E30, 51E12
Keywords: Strongly regular graphs, invariants, $k$-isoregularity, $t$-vertex condition, partial quadrangles, generalized quadrangles, partial linear spaces
Pech, Christian 1

1 Radebeul, Germany
License: CC-BY 4.0
Copyrights: The authors retain unrestricted copyrights and publishing rights 
@article{ALCO_2021__4_5_843_0,
     author = {Pech, Christian},
     title = {On highly regular strongly regular graphs},
     journal = {Algebraic Combinatorics},
     pages = {843--878},
     publisher = {MathOA foundation},
     volume = {4},
     number = {5},
     year = {2021},
     doi = {10.5802/alco.183},
     language = {en},
     url = {https://alco.centre-mersenne.org/articles/10.5802/alco.183/}
}
TY  - JOUR
AU  - Pech, Christian
TI  - On highly regular strongly regular graphs
JO  - Algebraic Combinatorics
PY  - 2021
SP  - 843
EP  - 878
VL  - 4
IS  - 5
PB  - MathOA foundation
UR  - https://alco.centre-mersenne.org/articles/10.5802/alco.183/
DO  - 10.5802/alco.183
LA  - en
ID  - ALCO_2021__4_5_843_0
ER  - 
%0 Journal Article
%A Pech, Christian
%T On highly regular strongly regular graphs
%J Algebraic Combinatorics
%D 2021
%P 843-878
%V 4
%N 5
%I MathOA foundation
%U https://alco.centre-mersenne.org/articles/10.5802/alco.183/
%R 10.5802/alco.183
%G en
%F ALCO_2021__4_5_843_0
Pech, Christian. On highly regular strongly regular graphs. Algebraic Combinatorics, Volume 4 (2021) no. 5, pp. 843-878. doi : 10.5802/alco.183. https://alco.centre-mersenne.org/articles/10.5802/alco.183/

[1] Bamberg, John; De Clerck, Frank; Durante, Nicola Intriguing sets in partial quadrangles, J. Combin. Des., Volume 19 (2011) no. 3, pp. 217-245 | DOI | MR | Zbl

[2] Bannai, Eiichi Maximal subgroups of low rank of finite symmetric and alternating groups, J. Fac. Sci. Univ. Tokyo Sect. IA Math., Volume 18 (1971/72), pp. 475-486 | MR

[3] Borceux, Francis Handbook of Categorical Algebra (Vol. 1), Encyclopedia of Mathematics and its Applications, 50, Cambridge University Press, Cambridge, 1994, xvi+345 pages | MR

[4] Bose, Raj C. Strongly regular graphs, partial geometries and partially balanced designs, Pacific J. Math., Volume 13 (1963), pp. 389-419 | MR

[5] Bose, Raj C.; Shrikhande, Sharadchandra S. Geometric and pseudo-geometric graphs (q 2 +1,q+1,1), J. Geom., Volume 2 (1972), pp. 75-94 | DOI | MR | Zbl

[6] Brouwer, Andries E. Parameters of Strongly Regular Graphs (https://www.win.tue.nl/~aeb/graphs/srg/srgtab.html)

[7] Brouwer, Andries E.; Ivanov, Andrei V.; Klin, Mikhail H. Some new strongly regular graphs, Combinatorica, Volume 9 (1989) no. 4, pp. 339-344 | DOI | MR | Zbl

[8] Buczak, J. M. J. Finite Group Theory, D.Phil. Thesis, Oxford University (1980)

[9] Cameron, Peter J. Partial quadrangles, Quart. J. Math. Oxford Ser. (2), Volume 26 (1975), pp. 61-73 | DOI | MR | Zbl

[10] Cameron, Peter J. 6-transitive graphs, J. Combin. Theory Ser. B, Volume 28 (1980) no. 2, pp. 168-179 | DOI | MR | Zbl

[11] Cameron, Peter J.; Goethals, Jean-Marie; Seidel, Johan J. Strongly regular graphs having strongly regular subconstituents, J. Algebra, Volume 55 (1978) no. 2, pp. 257-280 | DOI | MR | Zbl

[12] Cossidente, Antonio Combinatorial structures in finite classical polar spaces, Surveys in combinatorics 2017 (London Math. Soc. Lecture Note Ser.), Volume 440, Cambridge Univ. Press, Cambridge, 2017, pp. 204-237 | MR

[13] Cossidente, Antonio; Penttila, Tim Hemisystems on the Hermitian surface, J. London Math. Soc. (2), Volume 72 (2005) no. 3, pp. 731-741 | DOI | MR | Zbl

[14] De Clerck, Frank; Van Maldeghem, Hendrik Some classes of rank 2 geometries, Handbook of incidence geometry, North-Holland, Amsterdam, 1995, pp. 433-475 | DOI | MR

[15] Evdokimov, Sergei; Ponomarenko, Ilia Separability number and Schurity number of coherent configurations, Electron. J. Combin., Volume 7 (2000), Paper no. R31, 33 pages | MR

[16] Faradžev, Igor A.; Klin, Mikhail H.; Muzichuk, Mikhail E. Cellular rings and groups of automorphisms of graphs, Investigations in algebraic theory of combinatorial objects (Math. Appl. (Soviet Ser.)), Volume 84, Kluwer Acad. Publ., Dordrecht, 1994, pp. 1-152 | DOI | MR

[17] Fon-Der-Flaass, Dmitry G. New prolific constructions of strongly regular graphs, Adv. Geom., Volume 2 (2002) no. 3, pp. 301-306 | MR

[18] GAP – Groups, Algorithms, and Programming, Version 4.11.1 (2021) (https://www.gap-system.org)

[19] Gardiner, Anthony Homogeneous graphs, J. Combinatorial Theory Ser. B, Volume 20 (1976) no. 1, pp. 94-102 | DOI | MR | Zbl

[20] Gavrilyuk, Alexander L.; Makhnev, Alexander A. On Krein graphs without triangles, Dokl. Math., Volume 72 (2005) no. 1, pp. 591-594 | Zbl

[21] Godsil, Chris; Royle, Gordon Algebraic graph theory, Graduate Texts in Mathematics, 207, Springer-Verlag, New York, 2001, xx+439 pages | DOI | MR

[22] Gol’fand, Jakov Ju.; Klin, Mikhail H. On k-homogeneous graphs, Algorithmic studies in combinatorics (Russian), Nauka, Moscow, 1978, p. 76-85, 186 (errata insert) | MR

[23] Harary, Frank Graph theory, Addison-Wesley Publishing Co., Reading, Mass.-Menlo Park, Calif.-London, 1969, ix+274 pages

[24] Hestenes, Marshall D.; Higman, Donald G. Rank 3 groups and strongly regular graphs, Computers in algebra and number theory (Proc. SIAM-AMS Sympos. Appl. Math., New York, 1970) (SIAM-AMS Proc.), Volume IV, Amer. Math. Soc., Providence, R.I., 1971, pp. 141-159 | MR

[25] Higman, Donald G. Partial geometries, generalized quadrangles and strongly regular graphs, Atti del Convegno di Geometria Combinatoria e sue Applicazioni (Univ. Perugia, Perugia, 1970) (1971), pp. 263-293 | MR

[26] Higman, Donald G. Invariant relations, coherent configurations and generalized polygons, Combinatorics (Proc. Advanced Study Inst., Breukelen, 1974), Part 3: Combinatorial group theory (Math. Centre Tracts), Volume 57 (1974), pp. 27-43

[27] Ivanov, Alexander A.; Shpectorov, Sergey V. A characterization of the association schemes of Hermitian forms, J. Math. Soc. Japan, Volume 43 (1991) no. 1, pp. 25-48 | DOI | MR | Zbl

[28] Ivanov, Andrei V. Non-rank-3 strongly regular graphs with the 5-vertex condition, Combinatorica, Volume 9 (1989) no. 3, pp. 255-260 | DOI | MR | Zbl

[29] Ivanov, Andrei V. Two families of strongly regular graphs with the 4-vertex condition, Discrete Math., Volume 127 (1994) no. 1-3, pp. 221-242 Graph theory and applications (Hakone, 1990) | DOI | MR | Zbl

[30] Kantor, William M. Generalized quadrangles associated with G 2 (q), J. Combin. Theory Ser. A, Volume 29 (1980) no. 2, pp. 212-219 | DOI | MR | Zbl

[31] Kantor, William M. Some generalized quadrangles with parameters q 2 , q, Math. Z., Volume 192 (1986) no. 1, pp. 45-50 | DOI | MR | Zbl

[32] Kantor, William M.; Liebler, Robert A. The rank 3 permutation representations of the finite classical groups, Trans. Amer. Math. Soc., Volume 271 (1982) no. 1, pp. 1-71 | DOI | MR | Zbl

[33] Kaski, Petteri; Khatirinejad, Mahdad; Östergård, Patric R. J. Steiner triple systems satisfying the 4-vertex condition, Des. Codes Cryptogr., Volume 62 (2012) no. 3, pp. 323-330 | DOI | MR | Zbl

[34] Klin, Mikhail; Kriger, Nimrod; Woldar, Andrew Classification of highly symmetrical translation loops of order 2p, p prime, Beitr. Algebra Geom., Volume 55 (2014) no. 1, pp. 253-276 | DOI | MR | Zbl

[35] Klin, Mikhail; Meszka, Mariusz; Reichard, Sven; Rosa, Alex The smallest non-rank 3 strongly regular graphs which satisfy the 4-vertex condition, Bayreuth. Math. Schr. (2005) no. 74, pp. 145-205 | MR

[36] Klin, Mikhail H.; Woldar, Andrew J. The strongly regular graph with parameters (100,22,0,6): hidden history and beyond, Acta Univ. M. Belii Ser. Math., Volume 25 (2017), pp. 5-62 | MR

[37] Kováčiková, Kristína Induced Subgraphs in Strongly Regular Graphs, Dissertation Thesis, Comenius University in Bratislava (2015)

[38] Kriger, Nimrod Investigation of Strongly Regular Graphs of Latin Square Type and Related Combinatorial Objects, D.Phil. Thesis, Ben-Gurion University of the Negev (2015)

[39] Liebeck, Martin W.; Saxl, Jan The finite primitive permutation groups of rank three, Bull. London Math. Soc., Volume 18 (1986) no. 2, pp. 165-172 | DOI | MR | Zbl

[40] Mac Lane, Saunders Categories for the working mathematician, Graduate Texts in Mathematics, 5, Springer-Verlag, New York, 1998, xii+314 pages | MR

[41] Macpherson, Dugald A survey of homogeneous structures, Discrete Math., Volume 311 (2011) no. 15, pp. 1599-1634 | DOI | MR | Zbl

[42] McKay, Brendan D.; Piperno, Adolfo Practical graph isomorphism, II, J. Symbolic Comput., Volume 60 (2014), pp. 94-112 | DOI | MR | Zbl

[43] Muzychuk, Mikhail A generalization of Wallis-Fon-Der-Flaass construction of strongly regular graphs, J. Algebraic Combin., Volume 25 (2007) no. 2, pp. 169-187 | DOI | MR | Zbl

[44] Nešetřil, Jaroslav Amalgamation of graphs and its applications, Second International Conference on Combinatorial Mathematics (New York, 1978) (Ann. New York Acad. Sci.), Volume 319, New York Acad. Sci., New York, 1979, pp. 415-428 | MR

[45] Pasechnik, Dmitrii V. Skew-symmetric association schemes with two classes and strongly regular graphs of type L 2n-1 (4n-1), Acta Appl. Math., Volume 29 (1992) no. 1-2, pp. 129-138 (Interactions between algebra and combinatorics) | DOI | MR | Zbl

[46] Payne, Stanley E. Collineations of the generalized quadrangles associated with q-clans, Combinatorics ’90 (Gaeta, 1990) (Ann. Discrete Math.), Volume 52, North-Holland, Amsterdam, 1992, pp. 449-461 | DOI | MR

[47] Payne, Stanley E.; Thas, Joseph A. Finite generalized quadrangles, EMS Series of Lectures in Mathematics, European Mathematical Society (EMS), Zürich, 2009, xii+287 pages | DOI | MR | Zbl

[48] Pech, Christian; Pech, Maja On a family of highly regular graphs by Brouwer, Ivanov, and Klin, Discrete Math., Volume 342 (2019) no. 5, pp. 1361-1377 | DOI | MR | Zbl

[49] Reichard, Sven A criterion for the t-vertex condition of graphs, J. Combin. Theory Ser. A, Volume 90 (2000) no. 2, pp. 304-314 | DOI | MR | Zbl

[50] Reichard, Sven Computational and Theoretical Analysis of Coherent Configurations and Related Incidence Structures, Ph.D Thesis, University of Delaware (2003)

[51] Reichard, Sven Strongly regular graphs with the 7-vertex condition, J. Algebraic Combin., Volume 41 (2015) no. 3, pp. 817-842 | DOI | MR | Zbl

[52] Segre, Beniamino Forme e geometrie hermitiane, con particolare riguardo al caso finito, Ann. Mat. Pura Appl. (4), Volume 70 (1965), pp. 1-201 | DOI | MR | Zbl

[53] Slater, Peter J. A classification of 4-connected graphs, J. Combinatorial Theory Ser. B, Volume 17 (1974), pp. 281-298 | DOI | MR | Zbl

[54] Soicher, Leonard H. GRAPE, GRaph Algorithms using PErmutation groups, Version 4.8.5 (2021) (Refereed GAP package), https://gap-packages.github.io/grape

[55] Tits, Jacques Sur la trialité et certains groupes qui s’en déduisent, Inst. Hautes Études Sci. Publ. Math. (1959) no. 2, pp. 13-60 | MR

[56] Tutte, William T. A theory of 3-connected graphs, Nederl. Akad. Wetensch. Proc. Ser. A 64 = Indag. Math., Volume 23 (1961), pp. 441-455 | MR

[57] van Dam, Edwin R.; Martin, William J.; Muzychuk, Mikhail Uniformity in association schemes and coherent configurations: cometric Q-antipodal schemes and linked systems, J. Combin. Theory Ser. A, Volume 120 (2013) no. 7, pp. 1401-1439 | DOI | MR | Zbl

[58] Wallis, Walter D. Construction of strongly regular graphs using affine designs, Bull. Austral. Math. Soc., Volume 4 (1971), pp. 41-49 | DOI | MR | Zbl

Cited by Sources: