Printable PDF
Department of Mathematics,
University of California San Diego

****************************

Food For Thought Seminar

Daniel Kroes

UCSD

The edge reconstruction of graphs

Abstract:

In 1942 Kelly conjectured that any graph having at least 3 vertices is uniquely determined by the multiset of all its subgraphs obtained by deleting a vertex and all edges adjacent to it. In 1964 Harary conjectured analogously that any graph having at least 4 edges is uniquely determined by all its subgraphs obtained by deleting a single edge, which is known as the edge reconstruction conjecture. As of today, both conjectures are still open. In the talk I will discuss some of the classical results about the conjectures and some evidence in favor of them. Also I will explicitly show that the edge reconstruction conjecture holds for a specific type of graphs.

October 3, 2016

12:00 PM

AP&M 7321

****************************