2019-10-10 Alexandr V. Kostochka, Reconstructing graphs from smaller subgraphs

IBS Discrete Mathematics Group
Discrete Math Seminar
Alexandr V. Kostochka, Reconstructing graphs from smaller subgraphs
October 10 2019, Thursday @ 4:30 PM ~ 5:30 PM
Room B232, IBS (기초과학연구원)
Speaker
Alexandr V. Kostochka
University of Illinois at Urbana-Champaign
faculty.math.illinois.edu/~ko...
A graph or graph property is $l$-reconstructible if it is determined by the multiset of all subgraphs obtained by deleting $l$ vertices. Apart from the famous Graph Reconstruction Conjecture, Kelly conjectured in 1957 that for each $l \in \mathbb{N}$, there is an integer $n=n(l)$ such that every graph with at least $n$ vertices is $l$-reconstructible.
We show that for each $n \geq 7$ and every $n$-vertex graph $G$, the degree list and connectedness of $G$ are 3-reconstructible, and the threshold $n \geq 7$ is sharp for both properties.‌ We also show that all 3-regular graphs are 2-reconstructible.