Alexandr V. Kostochka, Reconstructing graphs from smaller subgraphs

IBS/KAIST Joint Discrete Math Seminar

Reconstructing graphs from smaller subgraphs
Alexandr V. Kostochka
University of Illinois at Urbana-Champaign
2019/10/10 Thu 4:30PM-5:30PM
A graph or graph property is $\ell$-reconstructible if it is determined by the multiset of all subgraphs obtained by deleting $\ell$ vertices. Apart from the famous Graph Reconstruction Conjecture, Kelly conjectured in 1957 that for each $\ell\in\mathbb N$, there is an integer $n=n(\ell)$ such that every graph with at least $n$ vertices is $\ell$-reconstructible. We show that for each $n\ge7$ 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.


Comments are closed.