A Lower Bound for the Weisfeiler-Leman Dimension of Circulant Graphs
Abstract
It is proved that for infinitely many positive integers $n$, there exists a circulant graph of order $n$ whose Weisfeiler-Leman dimension is at least $c\sqrt{\log n}$ for some constant $c>0$ not depending on $n$.
Fields of Study & Subjects
Graph theory and applications
Graph Labeling and Dimension Problems
Finite Group Theory Research
Publication details
- Journal / source
- The Electronic Journal of Combinatorics
- Volume
- 33
- Issue
- 2
- Publication date
- 5 June 2026
- Language
- EN