Reconstructing graphs

Algebra/Topology seminar

Speaker: Janne Kool. MPI Bonn.

Abstract: The famous Ulam-Kelly conjecture from the forties states that a graph is uniquely determined by the edge deck of the graph, which is the multi-set of graphs obtained from the original graph by one by deleting one of the edges. In this talk I will present how to find uniqueness of a reconstruction if the average degree is more then four, and some other technical conditions are satisfied, using Patterson-Sullivan measures on the boundary of the universal covering of the graph (Joint work with Gunther Cornelissen).