A new construction of strongly regular graphs with parameters of the complement symplectic graph

DOI10.37236/11343MaRDI QIDQ2684897zbMATH OpenOpenAlexFDO

Authors Vladislav Kabanov

Publication date 17 February 2023

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/2203.03921

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

divisible design graphstrongly regular graph

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Association schemes, strongly regular graphs (05E30)

Review text

The author describes a general procedure to obtain many divisible design graphs and strongly regular graphs (SRGs) coming from affine designs. In particular, a new construction for an SRG with the same parameters as the symplectic graph is obtained. Prolific constructions of such graphs have been obtained recently by switching in [\textit{F. Ihringer}, J. Algebr. Comb. 46, No. 2, 263--274 (2017; Zbl 1371.05321)]. Divisible design graphs were introduced in [\textit{W. H. Haemers} et al., J. Comb. Theory, Ser. A 118, No. 3, 978--992 (2011; Zbl 1232.05131)] in order to investigate connections between combinatorial designs and (algebraic) graph theory. Based on ideas from well-known prolific constructions of SRGs by \textit{W. D. Wallis} [Bull. Aust. Math. Soc. 4, 41--49 (1971; Zbl 0203.30802)], \textit{D. G. Fon-Der-Flaass} [Adv. Geom. 2, No. 3, 301--306 (2002; Zbl 1012.05158)], and \textit{M. Muzychuk} [J. Algebr. Comb. 25, No. 2, 169--187 (2007; Zbl 1111.05101)] (all independently), the author describes a construction for divisible design graphs based on affine designs. Two constructions for SRGs are then described, one using the former class of graphs as a building block, the other based on Hoffman colorings. For certain small parameter tuples such as (35,18,9,9), exhaustive computer searches have found all 3854 SRGs [\textit{B. D. McKay} and \textit{E. Spence}, Australas. J. Comb. 24, 293--300 (2001; Zbl 0979.05110)]. With this general construction, the author manages to recover a sizable proportion of them, in this case, 499 of them. However, it remains unclear how many non-isomorphic constructions the result provides in general.

Recommendations

• Symplectic graphs and their automorphisms
• Switched graphs of some strongly regular graphs related to the symplectic graph
• New versions of the Wallis-Fon-Der-Flaass construction to create divisible design graphs
• Strongly regular graphs with the same parameters as the symplectic graph
• scientific article; zbMATH DE number 1817540

Cites work

• A generalization of Wallis--Fon-Der-Flaass construction of strongly regular graphs
• A switching for all strongly regular collinearity graphs from polar spaces
• Classification of regular two-graphs on 36 and 38 vertices
• Construction of strongly regular graphs using affine designs
• Deza graphs based on symplectic spaces
• Divisible design graphs
• scientific article; zbMATH DE number 1817540 (Why is no real title available?)
• scientific article; zbMATH DE number 3349875 (Why is no real title available?)
• scientific article; zbMATH DE number 2232233 (Why is no real title available?)
• New versions of the Wallis-Fon-Der-Flaass construction to create divisible design graphs
• Regular graphs with four eigenvalues
• Strongly regular graphs
• Strongly regular graphs with strongly regular decomposition
• Switched symplectic graphs and their 2-ranks
• The strongly regular (40, 12, 2, 4) graphs

Cited in

(10)

• Symplectic graphs and their automorphisms
• scientific article; zbMATH DE number 1817540 (Why is no real title available?)
• A new construction of strongly regular graphs with parameters of the complement symplectic graph
• Strongly regular graphs decomposable into a divisible design graph and a Hoffman coclique
• Divisible design graphs from symplectic graphs over rings with a unique non-trivial ideal
• Strongly regular graphs decomposable into a divisible design graph and a Delsarte clique
• Divisible design graphs from the symplectic graph
• A large family of strongly regular graphs with small Weisfeiler-Leman dimension
• Divisible design graphs obtained by plugging a difference set into a construction for antipodal distance-regular graphs of diameter 3
• Non-commutative association schemes having divisible design graphs as relations from pseudo-cyclic association schemes

This page was built for publication: A new construction of strongly regular graphs with parameters of the complement symplectic graph

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2684897)