In this paper we unify several existing regularity conditions for graphs, including strong regularity, -isoregularity, and the -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 -vertex condition fulfills an even stronger condition, -regularity (the notion is defined in the text). Derived from this family we obtain a new infinite family of non rank strongly regular graphs satisfying the -vertex condition. This strengthens and generalizes previous results by Reichard.
Revised:
Accepted:
Published online:
Keywords: Strongly regular graphs, invariants, $k$-isoregularity, $t$-vertex condition, partial quadrangles, generalized quadrangles, partial linear spaces
@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 = {http://www.numdam.org/articles/10.5802/alco.183/} }
Pech, Christian. On highly regular strongly regular graphs. Algebraic Combinatorics, Volume 4 (2021) no. 5, pp. 843-878. doi : 10.5802/alco.183. http://www.numdam.org/articles/10.5802/alco.183/
[1] Intriguing sets in partial quadrangles, J. Combin. Des., Volume 19 (2011) no. 3, pp. 217-245 | DOI | MR | Zbl
[2] 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] Handbook of Categorical Algebra (Vol. 1), Encyclopedia of Mathematics and its Applications, 50, Cambridge University Press, Cambridge, 1994, xvi+345 pages | MR
[4] Strongly regular graphs, partial geometries and partially balanced designs, Pacific J. Math., Volume 13 (1963), pp. 389-419 | MR
[5] Geometric and pseudo-geometric graphs , J. Geom., Volume 2 (1972), pp. 75-94 | DOI | MR | Zbl
[6] Parameters of Strongly Regular Graphs (https://www.win.tue.nl/~aeb/graphs/srg/srgtab.html)
[7] Some new strongly regular graphs, Combinatorica, Volume 9 (1989) no. 4, pp. 339-344 | DOI | MR | Zbl
[8] Finite Group Theory, D.Phil. Thesis, Oxford University (1980)
[9] Partial quadrangles, Quart. J. Math. Oxford Ser. (2), Volume 26 (1975), pp. 61-73 | DOI | MR | Zbl
[10] -transitive graphs, J. Combin. Theory Ser. B, Volume 28 (1980) no. 2, pp. 168-179 | DOI | MR | Zbl
[11] Strongly regular graphs having strongly regular subconstituents, J. Algebra, Volume 55 (1978) no. 2, pp. 257-280 | DOI | MR | Zbl
[12] 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] Hemisystems on the Hermitian surface, J. London Math. Soc. (2), Volume 72 (2005) no. 3, pp. 731-741 | DOI | MR | Zbl
[14] Some classes of rank geometries, Handbook of incidence geometry, North-Holland, Amsterdam, 1995, pp. 433-475 | DOI | MR
[15] Separability number and Schurity number of coherent configurations, Electron. J. Combin., Volume 7 (2000), R31, 33 pages | MR
[16] 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] 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] Homogeneous graphs, J. Combinatorial Theory Ser. B, Volume 20 (1976) no. 1, pp. 94-102 | DOI | MR | Zbl
[20] On Krein graphs without triangles, Dokl. Math., Volume 72 (2005) no. 1, pp. 591-594 | Zbl
[21] Algebraic graph theory, Graduate Texts in Mathematics, 207, Springer-Verlag, New York, 2001, xx+439 pages | DOI | MR
[22] On -homogeneous graphs, Algorithmic studies in combinatorics (Russian), Nauka, Moscow, 1978, p. 76-85, 186 (errata insert) | MR
[23] Graph theory, Addison-Wesley Publishing Co., Reading, Mass.-Menlo Park, Calif.-London, 1969, ix+274 pages
[24] Rank 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] Partial geometries, generalized quadrangles and strongly regular graphs, Atti del Convegno di Geometria Combinatoria e sue Applicazioni (Univ. Perugia, Perugia, 1970), Ist. Mat., Univ. Perugia, Perugia (1971), pp. 263-293 | MR
[26] 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] 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] Non-rank- strongly regular graphs with the -vertex condition, Combinatorica, Volume 9 (1989) no. 3, pp. 255-260 | DOI | MR | Zbl
[29] Two families of strongly regular graphs with the -vertex condition, Discrete Math., Volume 127 (1994) no. 1-3, pp. 221-242 Graph theory and applications (Hakone, 1990) | DOI | MR | Zbl
[30] Generalized quadrangles associated with , J. Combin. Theory Ser. A, Volume 29 (1980) no. 2, pp. 212-219 | DOI | MR | Zbl
[31] Some generalized quadrangles with parameters , , Math. Z., Volume 192 (1986) no. 1, pp. 45-50 | DOI | MR | Zbl
[32] The rank permutation representations of the finite classical groups, Trans. Amer. Math. Soc., Volume 271 (1982) no. 1, pp. 1-71 | DOI | MR | Zbl
[33] Steiner triple systems satisfying the 4-vertex condition, Des. Codes Cryptogr., Volume 62 (2012) no. 3, pp. 323-330 | DOI | MR | Zbl
[34] Classification of highly symmetrical translation loops of order , prime, Beitr. Algebra Geom., Volume 55 (2014) no. 1, pp. 253-276 | DOI | MR | Zbl
[35] 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] The strongly regular graph with parameters : hidden history and beyond, Acta Univ. M. Belii Ser. Math., Volume 25 (2017), pp. 5-62 | MR
[37] Induced Subgraphs in Strongly Regular Graphs, Dissertation Thesis, Comenius University in Bratislava (2015)
[38] Investigation of Strongly Regular Graphs of Latin Square Type and Related Combinatorial Objects, D.Phil. Thesis, Ben-Gurion University of the Negev, Beer-Sheva (2015)
[39] The finite primitive permutation groups of rank three, Bull. London Math. Soc., Volume 18 (1986) no. 2, pp. 165-172 | DOI | MR | Zbl
[40] Categories for the working mathematician, Graduate Texts in Mathematics, 5, Springer-Verlag, New York, 1998, xii+314 pages | MR
[41] A survey of homogeneous structures, Discrete Math., Volume 311 (2011) no. 15, pp. 1599-1634 | DOI | MR | Zbl
[42] Practical graph isomorphism, II, J. Symbolic Comput., Volume 60 (2014), pp. 94-112 | DOI | MR | Zbl
[43] 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] 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] Skew-symmetric association schemes with two classes and strongly regular graphs of type , Acta Appl. Math., Volume 29 (1992) no. 1-2, pp. 129-138 (Interactions between algebra and combinatorics) | DOI | MR | Zbl
[46] Collineations of the generalized quadrangles associated with -clans, Combinatorics ’90 (Gaeta, 1990) (Ann. Discrete Math.), Volume 52, North-Holland, Amsterdam, 1992, pp. 449-461 | DOI | MR
[47] Finite generalized quadrangles, EMS Series of Lectures in Mathematics, European Mathematical Society (EMS), Zürich, 2009, xii+287 pages | DOI | MR | Zbl
[48] 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] A criterion for the -vertex condition of graphs, J. Combin. Theory Ser. A, Volume 90 (2000) no. 2, pp. 304-314 | DOI | MR | Zbl
[50] Computational and Theoretical Analysis of Coherent Configurations and Related Incidence Structures, Ph.D Thesis, University of Delaware (2003)
[51] Strongly regular graphs with the 7-vertex condition, J. Algebraic Combin., Volume 41 (2015) no. 3, pp. 817-842 | DOI | MR | Zbl
[52] 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] A classification of -connected graphs, J. Combinatorial Theory Ser. B, Volume 17 (1974), pp. 281-298 | DOI | MR | Zbl
[54] GRAPE, GRaph Algorithms using PErmutation groups, Version 4.8.5 (2021) (Refereed GAP package), https://gap-packages.github.io/grape
[55] 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] A theory of -connected graphs, Nederl. Akad. Wetensch. Proc. Ser. A 64 = Indag. Math., Volume 23 (1961), pp. 441-455 | MR
[57] 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] Construction of strongly regular graphs using affine designs, Bull. Austral. Math. Soc., Volume 4 (1971), pp. 41-49 | DOI | MR | Zbl
Cited by Sources: