On the Weisfeiler-Leman dimension of circulant graphs

2024/06/22 by Yulai Wu, Wu, Yulai, Ilia Ponomarenko +1 · 1 citation
Computer Science · Mathematics · #05E30 05C60 05E18 #Combinatorics (math.CO) #F.2.2 #FOS: Mathematics #Finite Group Theory Research #Graph Labeling and Dimension Problems #Graph theory and applications

paper · pdf · doi:10.48550/arxiv.2406.15822

openalex publication_date 2024/06/22 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

A circulant graph is a 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 correctly tests the 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 Ω(n)+3, where Ω(n) is the number of prime divisors of~n.

Cited by

• A lower bound for the Weisfeiler-Leman dimension of circulant graphs

Related

• A lower bound for the Weisfeiler-Leman dimension of circulant graphs
• On the WL-dimension of circulant graphs of prime power order
• An Upper Bound on the Weisfeiler-Leman Dimension
• On the Weisfeiler-Leman dimension of permutation graphs
• A Linear Upper Bound on the Weisfeiler-Leman Dimension of Graphs of Bounded Genus