On $WL$-rank and $WL$-dimension of some circulant Deza graphs

The WL-rank $rk_{WL}(\Gamma)$ of a digraph $\Gamma$ is defined to be the number of classes in the coherent configuration of $\Gamma$. The graph $\Gamma$ is strongly regular if and only the $rk_{WL}(\Gamma)\leqslant 3$. All strongly regular circulant graphs, i.e. all circulant graphs of WL-rank at most $3$, were classified independently in [1,6,7].

A $k$-regular graph $\Gamma$ on $n$ vertices is called a Deza graph if there exist nonnegative integers $a$ and $b$ such that any pair of distinct vertices of $\Gamma$ has either $a$ or $b$ common neighbors [2]. A Deza graph is called strictly if it is non-strongly regular and has diameter $2$.

We classify Deza circulant graphs of WL-rank $4$. We also establish that some families of strictly Deza circulant graphs have WL-rank $5$ or $6$. Together with computational result [3.4], this implies that every strictly Deza circulant graph with at most $95$ vertices has WL-rank at most $6$.

The WL-dimension of a graph $\Gamma$ is defined to be the smallest positive integer $m$ for which $\Gamma$ is identified by the $m$-dimensional Weisfeiler-Leman algorithm [5, Definition 18.4.2]. We prove that all considered graphs have WL-dimension at most $3$. The talk is based on the results of paper [8]

\noindent Acknowledgement. The work is supported by the Mathematical Center in Akademgorodok under the agreement No. 075-15-2019-1613 with the Ministry of Science and Higher Education of the Russian Federation.

The is joint work with Viktor Panshin and Grigory Ryabov

Список литературы

1. W. Bridges, R. Mena, “Rational circulants with rational spectra and cyclic strongly regular graphs”, Ars Combin., 8 (1979), 143–161
2. M. Erickson, S. Fernando, W. Haemers, D. Hardy, J. Hemmeter, “Deza graphs: a generalization of strongly regular graphs”, J. Comb. Designs, 7 (1999), 359–405
3. A. Gavrilyuk, S. Goryainov, L. Shalaginov, Proceedings of G2A2-conference, Ekaterinburg, 2015 http://g2a2.imm.uran.ru/slides/plenary_talks/Goryainov.pdf
4. S. Goryainov, L. Shalaginov, “Cayley-Deza graphs with less than $60$ vertices”, Sib. Elect. Math. Rep., 11 (2014), 268–310
5. M. Gröhe,, Descriptive complexity, canonisation, and definable graph structure theory, Cambridge University Press, Cambridge, 2017
6. D. Hughes, J. van Lint, R. Wilson, 1979 (Announcement at the Seventh British Combinatorial Conference Cambridge (unpublished))
7. S. Ma, “Partial difference sets”, Discrete Math., 52 (1984), 75–89
8. R. Bildanov, V. Panshin, G. Ryabov, On WL-rank and WL-dimension of some Deza circulant graphs, arXiv: 2012.13898