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
****************************