On the Weisfeiler-Leman dimension of circulant graphs
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866912049317019648 |
|---|---|
| author | Wu, Yulai Ponomarenko, Ilia |
| author_facet | Wu, Yulai Ponomarenko, Ilia |
| contents | 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$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2406_15822 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | On the Weisfeiler-Leman dimension of circulant graphs Wu, Yulai Ponomarenko, Ilia Combinatorics 05E30 05C60 05E18 F.2.2 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$. |
| title | On the Weisfeiler-Leman dimension of circulant graphs |
| topic | Combinatorics 05E30 05C60 05E18 F.2.2 |
| url | https://arxiv.org/abs/2406.15822 |