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
Reykjavik University
Klas Markström
Umeå University
Andrzej Rucinski
Adam Mickiewicz University
Carsten Thomassen
Technical University of Denmark, DTU


Klas Markström


For practical matters at the Institute, send an e-mail to