5 papers
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 no…
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…
On a Hierarchy of Spectral Invariants for Graphs
V. Arvind, Frank Fuhlbrück, Johannes Köbler +1
We consider a hierarchy of graph invariants that naturally extends the spectral invariants defined by Fürer (Lin. Alg. Appl. 2010) based on the angles formed by the set of standar…
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 previo…