11 citations · 34 across the 14 of their papers we have counts for
7 papers · 1 filter
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).
Isomorphism testing of -spanning tournaments is Fixed Parameter Tractable
Vikraman Arvind, Ilia Ponomarenko, Grigory Ryabov
An arc-colored tournament is said to be -spanning for an integer if the union of its arc-color classes of maximal valency at most is the arc set of a strongly conn…
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…
Recognizing and testing isomorphism of Cayley graphs over an abelian group of order in polynomial time
Roman Nedela, Ilia Ponomarenko
We construct a polynomial-time algorithm that given a graph with vertices ( is prime), finds (if any) a Cayley representation of over the group $C_2\times C_2\times…
The basis digraphs of p-schemes
Ilia Ponomarenko, Amir Rahnamai Barghi
It is proved that association schemes with bipartite basis graphs are exactly 2-schemes. This result follows from a characterization of p-schemes for an arbitrary prime p in terms…
A modular absolute bound condition for primitive association schemes
Akihide Hanaki, Ilia Ponomarenko
The well-known absolute bound condition for a primitive symmetric association scheme (X,S) gives an upper bound for |X| in terms of |S| and the minimal non-principal multiplicity o…