4 papers
The automorphism groups and identification of some Generalized Paley Graphs
Ilia Ponomarenko
The family of generalized Paley graphs of prime power order and degree is studied. It is shown that the automorphism group of a graph in this family is a subgroup of…
A lower bound for the Weisfeiler-Leman dimension of circulant graphs
Yulai Wu, Qing Ren, Ilia Ponomarenko
It is proved that for infinitely many positive integers n, there exists a circulant graph of order n whose Weisfeiler-Leman dimension is at least c\sqrt{log n} for some positive co…
On the Weisfeiler algorithm of depth- stabilization
Gang Chen, Qing Ren, Ilia Ponomarenko
An origin of the multidimensional Weisfeiler-Leman algorithm goes back to a refinement procedure of deep stabilization, introduced by B. Weisfeiler in a paper included in the colle…
Walk refinement, walk logic, and the iteration number of the Weisfeiler-Leman algorithm
Moritz Lichter, Ilia Ponomarenko, Pascal Schweitzer
We show that the 2-dimensional Weisfeiler-Leman algorithm stabilizes n-vertex graphs after at most O(n log n) iterations. This implies that if such graphs are distinguishable in 3-…