|
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
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.
Received: 26.11.2024
Citation:
Yu. Wu, I. Ponomarenko, “On the Weisfeiler–Leman dimension of circulant graphs”, Algebra i Analiz, 37:2 (2025), 1–27
Linking options:
https://www.mathnet.ru/eng/aa1957 https://www.mathnet.ru/eng/aa/v37/i2/p1
|
Statistics & downloads: |
Abstract page: | 92 | Full-text PDF : | 1 | References: | 14 | First page: | 9 |
|