RUS  ENG
Full version
JOURNALS // Zapiski Nauchnykh Seminarov POMI // Archive

Zap. Nauchn. Sem. POMI, 2022 Volume 518, Pages 152–172 (Mi znsl7296)

On WL-rank and WL-dimension of some Deza dihedrants

G. K. Ryabova, L. V. Shalaginovb

a Sobolev Institute of Mathematics, Novosibirsk, Russia
b Chelyabinsk State University, Chelyabinsk, Russia

Abstract: The WL-rank of a graph $\Gamma$ is defined to be the rank of the coherent configuration of $\Gamma$. The WL-dimension of $\Gamma$ is defined to be the smallest positive integer $m$ for which $\Gamma$ is identified by the $m$-dimensional Weisfeiler-Leman algorithm. We present some families of strictly Deza dihedrants of WL-rank $4$ or $5$ and WL-dimension $2$. Computer calculations show that every strictly Deza dihedrant with at most $59$ vertices is circulant or belongs to one of the above families. We also construct a new infinite family of strictly Deza dihedrants whose WL-rank is a linear function of the number of vertices.

Key words and phrases: WL-rank, WL-dimension, Deza graphs, Cayley graphs, dihedral group.

UDC: 519.175.1, 512.542

Received: 26.09.2022

Language: English



© Steklov Math. Inst. of RAS, 2024