Geodesic
On WL-rank and WL-dimension of some Deza dihedrants
Zapiski Nauchnykh Seminarov POMI, Combinatorics and graph theory. Part XIII, Tome 518 (2022), pp. 152-172 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice du chapitre de livre

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. 
@article{ZNSL_2022_518_a4,
     author = {G. K. Ryabov and L. V. Shalaginov},
     title = {On {WL-rank} and {WL-dimension} of some {Deza} dihedrants},
     journal = {Zapiski Nauchnykh Seminarov POMI},
     pages = {152--172},
     year = {2022},
     volume = {518},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/ZNSL_2022_518_a4/}
}
TY  - JOUR
AU  - G. K. Ryabov
AU  - L. V. Shalaginov
TI  - On WL-rank and WL-dimension of some Deza dihedrants
JO  - Zapiski Nauchnykh Seminarov POMI
PY  - 2022
SP  - 152
EP  - 172
VL  - 518
UR  - http://geodesic.mathdoc.fr/item/ZNSL_2022_518_a4/
LA  - en
ID  - ZNSL_2022_518_a4
ER  - 
%0 Journal Article
%A G. K. Ryabov
%A L. V. Shalaginov
%T On WL-rank and WL-dimension of some Deza dihedrants
%J Zapiski Nauchnykh Seminarov POMI
%D 2022
%P 152-172
%V 518
%U http://geodesic.mathdoc.fr/item/ZNSL_2022_518_a4/
%G en
%F ZNSL_2022_518_a4
G. K. Ryabov; L. V. Shalaginov. On WL-rank and WL-dimension of some Deza dihedrants. Zapiski Nauchnykh Seminarov POMI, Combinatorics and graph theory. Part XIII, Tome 518 (2022), pp. 152-172. http://geodesic.mathdoc.fr/item/ZNSL_2022_518_a4/

[1] V. Arvind, J. Köbler, G. Rattan, O. Verbitsky, “Graph isomorphism, color refinement, and compactness”, Comput. Complex., 26:3 (2017), 627–685

[2] L. D. Baumert, Cyclic difference sets, Lect. Notes Math., 182, Springer-Verlag, 1971

[3] R. Bildanov, V. Panshin, G. Ryabov, “On WL-rank and WL-dimension of some Deza circulant graphs”, Graphs Combin., 37:6 (2021), 2397–2421

[4] G. Chen, I. Ponomarenko, Coherent configurations, Central China Normal University Press, Wuhan, 2019

[5] D. Churikov, G. Ryabov, “On WL-rank of Deza Cayley graphs”, Discrete Math., 345:2 (2022), 112692

[6] E. R. van Dam, “Three-class association schemes”, J. Algebraic Comb., 10 (1999), 69–107

[7] A. Deza, M. Deza, “The ridge graph of the metric polytope and some relatives”, Polytopes: Abstract, convex and computational, NATO ASI Series, eds. T. Bisztriczky et al., Kluwer Academic, 1994, 359–372

[8] 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

[9] S. Evdokimov, I. Ponomarenko, “On a family of Schur rings over a finite cyclic group”, St. Petersburg Math. J., 13:3 (2002), 441–451

[10] S. Evdokimov, I. Ponomarenko, “Schurity of $S$-rings over a cyclic group and generalized wreath product of permutation groups”, St. Petersburg Math. J., 24:3 (2013), 431–460

[11] F. Fuhlbrück, J Köbler, O. Verbitsky, “Identiability of graphs with small color classes by the Weisfeiler-Leman algorithm”, Proc. $37$th International Symposium on Theoretical Aspects of Computer Science, Dagstühl Publishing, Germany, 2020, 43:1–43:18

[12] A. L. Gavrilyuk, R. Nedela, I. Ponomarenko, The Weisfeiler–Leman dimension of distance-hereditary graphs, 2020, 16 pp., arXiv: 2005.11766 [math.CO]

[13] S. Goryainov, D. Panasenko, L. Shalaginov, Parameters of strictly Cayley-Deza graphs, http://alg.imm.uran.ru/dezagraphs/dezacayleytab.html

[14] S. Goryainov, D. Panasenko, L. Shalaginov, “Enumeration of strictly Deza graphs with at most 21 vertices”, Sib. Elect. Math. Rep., 18:2 (2021), 1423–1432

[15] S. Goryainov, L. Shalaginov, “Cayley-Deza graphs with less than $60$ vertices”, Sib. Elect. Math. Rep., 11 (2014), 268–310

[16] S. Goryainov, L. Shalaginov, Deza graphs: a survey and new results, 2021, 30 pp., arXiv: 2103.00228 [math.CO]

[17] M. Gröhe, Descriptive complexity, canonisation, and definable graph structure theory, Cambridge University Press, Cambridge, 2017

[18] M. Gröhe, D. Neuen, Recent advances on the graph isomorphism problem, 2020, 39 pp., arXiv: 2011.01366 [cs.DS]

[19] A. Hanaki, I. Miyamoto, Classification of association schemes with small number of vertices, , 2016 http://math.shinshu-u.ac.jp/h̃anaki/as/

[20] M. Klin, C. Pech, S. Reichard, COCO2P – a GAP package, 0.14, 07.02.2015 http://www.math.tu-dresden.de/p̃ech/COCO2P

[21] J. Morris, J. Smolčič, “Two families of graphs that are Cayley on nonisomorphic groups”, J. Algebra Comb. Discrete Appl., 8:1 (2021), 53–57

[22] Š. Miklavič, P. Potočnik, “Distance-regular Cayley graphs on dihedral groups”, J. Comb. Theory. Ser. B, 97 (2007), 14–33

[23] M. Muzychuk, I. Ponomarenko, “On Schur $2$-groups”, J. Math. Sci. (N.-Y.), 219:4 (2016), 565–594

[24] I. Ponomarenko, “On the separability of cyclotomic schemes over finite field”, St. Petersburg Math. J., 32:6 (2021), 1051–1066

[25] I. Ponomarenko, G. Ryabov, “The Weisfeiler–Leman dimension of chordal bipartite graphs without bipartite claw”, Graphs Combin., 37:3 (2021), 1089–1102

[26] I. Ponomarenko, A. Vasil'ev, “On nonabelian Schur groups”, J. Algebra Appl., 13:8 (2014), 1450055

[27] A. Pott, Finite geometry and character theory, Berlin, Springer-Verlag, 1995

[28] G. Ryabov, “On Schur p-groups of odd order”, J. Algebra Appl., 16:3 (2017), 1750045

[29] G. Ryabov, “On separability of Schur rings over abelian $p$-groups”, Algebra Log., 57:1 (2018), 49–68

[30] I. Schur, “Zur theorie der einfach transitiven Permutationgruppen”, S.-B. Preus Akad. Wiss. Phys.-Math. Kl., 18:20 (1933), 598–623

[31] L. Shalaginov, “Divisible design graphs with parameters $(4n,n+2,n-2,2,4,n)$ and $(4n,3n-2,3n-6,2n-2,4,n)$”, Sib. Elect. Math. Rep., 18:2 (2021), 1742–1756

[32] H. Wielandt, Finite permutation groups, Academic Press, New York–London, 1964

[33] B. Weisfeiler, A. Leman, “Reduction of a graph to a canonical form and an algebra which appears in the process”, NTI, 2:9 (1968), 12–16