Scholarlink

<p>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 <i>n</i> and a positive constant <i>c</i>, this family contains at least <InlineEquation ID="IEq1"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="493_2025_145_Article_IEq1.gif" Format="GIF" Height="20" Rendition="HTML" Resolution="72" Type="Linedraw" Width="42" /> </InlineMediaObject> <EquationSource Format="TEX">\(n^{c\cdot n^{2/3}}\)</EquationSource> <EquationSource Format="MATHML"><math> <msup> <mi>n</mi> <mrow> <mi>c</mi> <mo>·</mo> <msup> <mi>n</mi> <mrow> <mn>2</mn> <mo stretchy="false">/</mo> <mn>3</mn> </mrow> </msup> </mrow> </msup> </math></EquationSource> </InlineEquation> strongly regular <i>n</i>-vertex graphs&#xa0;<i>X</i> with the same parameters, which satisfy the following condition: an isomorphism between <i>X</i> and any other graph can be verified by the 4-dimensional Weisfeiler-Leman algorithm.</p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

A Large Family of Strongly Regular Graphs with Small Weisfeiler-Leman Dimension

  • 期刊论文

  • 发表日期：

    2025年3月24日

查看全文
  • Jinzhuan Cai,
  • Jin Guo,
  • Alexander L. Gavrilyuk,
  • Ilia Ponomarenko

摘要

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 and a positive constant c, this family contains at least \(n^{c\cdot n^{2/3}}\) n c · 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.