A lower bound for the Weisfeiler-Leman dimension of circulant graphs | Synapse
October 2, 2025Open Access
A lower bound for the Weisfeiler-Leman dimension of circulant graphs
Key Points
Circulant graphs exhibit a Weisfeiler-Leman dimension of at least c√log n for infinitely many positive integers n.
For some positive constant c, the dimension grows substantially with order n, emphasizing its mathematical significance.
The study establishes a lower bound for the Weisfeiler-Leman dimension of these graphs, expanding their theoretical understanding.
Implications extend theoretical limits regarding graph dimensions and contribute to graph theory research.
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 clog n for some positive constant c not depending on n.