# Alexandr V. Kostochka, Reconstructing graphs from smaller subgraphs

## October 10 Thursday @ 4:30 PM - 5:30 PM

Room B232, IBS (기초과학연구원)

### Speaker

Alexandr V. Kostochka
University of Illinois at Urbana-Champaign
https://faculty.math.illinois.edu/~kostochk/

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.

## Details

Date:
October 10 Thursday
Time:
4:30 PM - 5:30 PM
Event Category:
Event Tags:

Room B232
IBS (기초과학연구원)

## Organizer

Sang-il Oum
기초과학연구원 수리및계산과학연구단 이산수학그룹
대전 유성구 엑스포로 55 (우) 34126
IBS Discrete Mathematics Group (DIMAG)
Institute for Basic Science (IBS)
55 Expo-ro Yuseong-gu Daejeon 34126 South Korea
E-mail: dimag@ibs.re.kr