Algebra i Analiz
RUS  ENG    JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB  
General information
Latest issue
Archive
Impact factor

Search papers
Search references

RSS
Latest issue
Current issues
Archive issues
What is RSS



Algebra i Analiz:
Year:
Volume:
Issue:
Page:
Find






Personal entry:
Login:
Password:
Save password
Enter
Forgotten password?
Register


Algebra i Analiz, 2025, Volume 37, Issue 2, Pages 1–27 (Mi aa1957)  

Research Papers

On the Weisfeiler–Leman dimension of circulant graphs

Yu. Wua, I. Ponomarenkoab

a School of Mathematics and Statistics, Hainan University, Haikou, China
b Steklov Institute of Mathematics at St. Petersburg, Russia
References:
Abstract: A circulant graph is the Cayley graph of a finite cyclic group. The Weisfeiler–Leman dimension of a circulant graph $X$ with respect to the class of all circulant graphs is the smallest positive integer $m$ such that the $m$-dimensional Weisfeiler–Leman algorithm properly tests isomorphism between $X$ and any other circulant graph. It is proved that for a circulant graph of order $n$ this dimension is less than or equal to $\Omega(n)+3$, where $\Omega(n)$ is the total number of prime divisors of $n$.
Keywords: ciculant graph, Weisfeiler–Leman dimension, coherent configuration, Cayley scheme.
Funding agency Grant number
Hainan Provincial Natural Science Foundation of China 120RC452
Natural Science Foundation of China 12361003
Yulai Wu: Partly supported by Hainan Province Natural Science Foundation of China, grant No. 120RC452. I. Ponomarenko: Supported by Natural Science Foundation of China, grant No. 12361003.
Received: 26.11.2024
Document Type: Article
Language: English
Citation: Yu. Wu, I. Ponomarenko, “On the Weisfeiler–Leman dimension of circulant graphs”, Algebra i Analiz, 37:2 (2025), 1–27
Citation in format AMSBIB
\Bibitem{WuPon25}
\by Yu.~Wu, I.~Ponomarenko
\paper On the Weisfeiler--Leman dimension of circulant graphs
\jour Algebra i Analiz
\yr 2025
\vol 37
\issue 2
\pages 1--27
\mathnet{http://mi.mathnet.ru/aa1957}
Linking options:
  • https://www.mathnet.ru/eng/aa1957
  • https://www.mathnet.ru/eng/aa/v37/i2/p1
  • Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    Алгебра и анализ St. Petersburg Mathematical Journal
    Statistics & downloads:
    Abstract page:92
    Full-text PDF :1
    References:14
    First page:9
     
      Contact us:
     Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2025