10 citations · 44 across the 41 of their papers we have counts for
48 papers
Gathering Information about a Graph by Counting Walks from a Single Vertex
Frank Fuhlbrück, Johannes Köbler, Oleg Verbitsky +1
We say that a vertex in a connected graph is decisive if the numbers of walks from of each length determine the graph rooted at up to isomorphism among all conn…
Canonical labelling of sparse random graphs
Oleg Verbitsky, Maksim Zhukovskii
We show that if , then the Erdős-Rényi random graph with high probability admits a canonical labeling computable in time . Combined with the previous…
New bounds for the optimal density of covering single-insertion codes via the Turán density
Oleg Pikhurko, Oleg Verbitsky, Maksim Zhukovskii
We prove that the density of any covering single-insertion code over the -symbol alphabet cannot be smaller than for some positive real not…
On the Expressibility of the Reconstructional Color Refinement
V. Arvind, Johannes Köbler, Oleg Verbitsky
One of the most basic facts related to the famous Ulam reconstruction conjecture is that the connectedness of a graph can be determined by the deck of its vertex-deleted subgraphs,…
Canonization of a random graph by two matrix-vector multiplications
Oleg Verbitsky, Maksim Zhukovskii
We show that a canonical labeling of a random -vertex graph can be obtained by assigning to each vertex the triple , where is the number of…
Canonization of a random circulant graph by counting walks
Oleg Verbitsky, Maksim Zhukovskii
It is well known that almost all graphs are canonizable by a simple combinatorial routine known as color refinement, also referred to as the 1-dimensional Weisfeiler-Leman algorith…