Статьи

On the Weisfeiler–Leman dimension of circulant graphs

[О размерности Вейсфейлера–Лемана циркулянтных графов]

Yu. Wu^a, I. Ponomarenko<sup>ab

a</sup> School of Mathematics and Statistics, Hainan University, Haikou, China
^b Steklov Institute of Mathematics at St. Petersburg, Russia

Аннотация: Циркулянтным графом называется любой граф Кэли над конечной циклической группой. Под размерностью Вейсфейлера-Лемана циркулянтного графа $X$ относительно класса всех циркулянтных графов понимается наименьшее положительное целое число $m$, такое что $m$-мерный алгоритм Вейсфейлера-Лемана корректно проверяет изоморфизм между $X$ и любым другим циркулянтным графом. Доказано, что для циркулянтного графа порядка $n$ эта размерность меньше или равна $\Omega(n)+3$, где $\Omega(n)$ – общее число простых делителей числа $n$.

Ключевые слова: цикулянтный граф, размерность Вейсфейлера-Лемана, когерентная конфигурация, схема Кэли.

Поступила в редакцию: 26.11.2024

Язык публикации: английский