On the reconstruction of a graph with large diameter
Graphs, Hypergraphs, and Computing
29 April 14:00 - 15:00
Helge Tverberg - University of Bergen
Let G=(V,E) be an undirected graph with n vertices and m edges,without loops or multiple edges.S.Ulam conjectured that if n>2,the knowledge of the structure of each of the n subgraphs G-v,allows one to find the structure of G. The conjecture is still unproved,but it is known to hold for many classes of graphs.
In this talk I shall describe parts of two unpublished Master theses by respectively Joar Loland (1983,in Norwegian) and Erik Naze Tjøtta (1991,in English),which deserve to be better known.In the last one it is proved that the conjecture holds for all graphs of diameter at least [n/2]+1.Tjøtta builds on Loland's result that the assumption on the diameter allows one to reconstruct it.I shall also say something about what happens if [n/2]+1 is replaced by [n/2].
Magnus M. Halldorsson
Adam Mickiewicz University
Technical University of Denmark, DTU