Geodesic
On the WL-dimension of circulant graphs of prime power order
Ponomarenko, Ilia1
1 Steklov Institute of Mathematics at St. Petersburg, Russia
Algebraic Combinatorics, Tome 6 (2023) no. 6, pp. 1469-1490

Voir la notice de l'article provenant de la source Numdam

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.

Reçu le :
Révisé le :
Accepté le :
Publié le :
DOI : 10.5802/alco.315
Classification : 05C60, 05E30
Keywords: Weisfeiler–Leman algorithm, circulant graphs, coherent configurations

Ponomarenko, Ilia 1

1 Steklov Institute of Mathematics at St. Petersburg, Russia
Licence : CC-BY 4.0
Droits d'auteur : Les auteurs conservent leurs droits 
@article{ALCO_2023__6_6_1469_0,
     author = {Ponomarenko, Ilia},
     title = {On the {WL-dimension} of circulant graphs of prime power order},
     journal = {Algebraic Combinatorics},
     pages = {1469--1490},
     publisher = {The Combinatorics Consortium},
     volume = {6},
     number = {6},
     year = {2023},
     doi = {10.5802/alco.315},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.5802/alco.315/}
}
TY  - JOUR
AU  - Ponomarenko, Ilia
TI  - On the WL-dimension of circulant graphs of prime power order
JO  - Algebraic Combinatorics
PY  - 2023
SP  - 1469
EP  - 1490
VL  - 6
IS  - 6
PB  - The Combinatorics Consortium
UR  - http://geodesic.mathdoc.fr/articles/10.5802/alco.315/
DO  - 10.5802/alco.315
LA  - en
ID  - ALCO_2023__6_6_1469_0
ER  - 
%0 Journal Article
%A Ponomarenko, Ilia
%T On the WL-dimension of circulant graphs of prime power order
%J Algebraic Combinatorics
%D 2023
%P 1469-1490
%V 6
%N 6
%I The Combinatorics Consortium
%U http://geodesic.mathdoc.fr/articles/10.5802/alco.315/
%R 10.5802/alco.315
%G en
%F ALCO_2023__6_6_1469_0
Ponomarenko, Ilia. On the WL-dimension of circulant graphs of prime power order. Algebraic Combinatorics, Tome 6 (2023) no. 6, pp. 1469-1490. doi: 10.5802/alco.315

Cité par Sources :