Showing cs.DMShow all
2 papers · 1 filter
cs.DM2024
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…
cs.DM2024
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…