|
Zapiski Nauchnykh Seminarov 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.
Received: 26.09.2022
Citation:
G. K. Ryabov, L. V. Shalaginov, “On WL-rank and WL-dimension of some Deza dihedrants”, Combinatorics and graph theory. Part XIII, Zap. Nauchn. Sem. POMI, 518, POMI, St. Petersburg, 2022, 152–172
Linking options:
https://www.mathnet.ru/eng/znsl7296 https://www.mathnet.ru/eng/znsl/v518/p152
|
Statistics & downloads: |
Abstract page: | 51 | Full-text PDF : | 10 | References: | 19 |
|