A large family of strongly regular graphs with small Weisfeiler-Leman dimension

2023/12/01 by Cai, Jinzhuan, Guo, Jin, Gavrilyuk, Alexander L. +1 · 1 citation
#Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.2312.00460

Abstract

In 2002, D. Fon-Der-Flaass constructed a prolific family of strongly regular graphs. In this paper, we prove that for infinitely many natural numbers n, this family contains n^Ω(n^2/3) strongly regular n-vertex graphs X with the same parameters, which satisfy the following condition: an isomorphism between X and any other graph can be verified by the 4-dimensional Weisfeiler-Leman algorithm.

Cited by

• The automorphism groups and identification of some Generalized Paley Graphs

Related

• There is no strongly regular graph with parameters (460,153,32,60)
• On a family of strongly regular graphs with λ=1
• On highly regular strongly regular graphs
• Local WL Invariance and Hidden Shades of Regularity
• An Upper Bound on the Weisfeiler-Leman Dimension