"Записки научных семинаров ПОМИ"
Том 518, стр. 152-172
О WL-ранге и WL-размерности некоторых диэдрантов Деза
Г. К. Рябов, Л. В. Шалагинов
Sobolev Institute of Mathematics, Novosibirsk, Russia
gric2ryabov@gmail.com
Chelyabinsk State University, Chelyabinsk, Russia
44sh@mail.ru
- Аннотация:
\emph{WL-рангом} графа $\Gamma$ называется ранг когерентной конфигурации графа $\Gamma$.
\emph{WL-размерностью} графа $\Gamma$ называется наименьшее натуральное число~$m$,
для которого $\Gamma$ может быть идентифицирован $m$-мерным алгоритмом Вейсфейлера--Лемана.
В настоящей статье описаны некоторые семейства точных диэдрантов Деза $WL$-ранга~$4$ или $5$
и $WL$-размерности $2$. Компьютерные вычисления показывают,
что каждый точный диэдрант Деза с не более чем 59 вершинами изоморфен циркулянту или принадлежит
одному из описанных семейств. Также в статье строится новая бесконечная серия точных диэдрантов Деза,
$WL$-ранг которых является линейной функцией от числа вершин.
Библ. -- 33 назв.
- Ключевые слова: WL-ранг, WL-размерность, графы Деза, графы Кэли, группы диэдра
[WL-rank, WL-dimension, Deza graphs, Cayley graphs, dihedral group]
Полный текст(.pdf)