On the WL-dimension of circulant graphs of prime power order
Ilia Nikolaevich Ponomarenko · Algebraic Combinatorics · 2024
The WL -dimension of a graph X is the smallest positive integer m such that the m -dimensional Weisfeiler–Leman algorithm correctly tests the isomorphism between X and any other graph. It is proved that the WL -dimension of any circulant graph of prime power order is at most 3 , and this bound cannot be reduced. The proof is based on using theories of coherent configurations and Cayley schemes over a cyclic group.