5 papers
Cartesian products of graphs and their coherent configurations
Jinzhuan Cai, Jin Guo, Alexander L. Gavrilyuk +1
The coherent configuration of a graph is the smallest coherent configuration on the vertices of that contains the edge set of as a relation. The aim of…
A linear programming bound for sum-rank metric codes
Aida Abiad, Alexander L. Gavrilyuk, Antonina P. Khramova +1
We derive a linear programming bound on the maximum cardinality of error-correcting codes in the sum-rank metric. Based on computational experiments on relatively small instances,…
A large family of strongly regular graphs with small Weisfeiler-Leman dimension
Jinzhuan Cai, Jin Guo, Alexander L. Gavrilyuk +1
In 2002, D. Fon-Der-Flaass constructed a prolific family of strongly regular graphs. In this paper, we prove that for infinitely many natural numbers , this family contains $n^{…
On the Weisfeiler-Leman dimension of permutation graphs
Jin Guo, Alexander L. Gavrilyuk, Ilia Ponomarenko
It is proved that the Weisfeiler-Leman dimension of the class of permutation graphs is at most 18. Previously it was only known that this dimension is finite (Grußien, 2017).
The Weisfeiler-Leman dimension of distance-hereditary graphs
Alexander L. Gavrilyuk, Roman Nedela, Ilia Ponomarenko
A graph is said to be distance-hereditary if the distance function in every connected induced subgraph is the same as in the graph itself. We prove that the ordinary Weisfeiler-Lem…