# 2022 Combinatorics Workshop

September 30, 2022 to October 1, 2022
Asia/Seoul timezone

## Reconstruction and Edge Reconstruction of Triangle-free Graphs

Sep 30, 2022, 4:45 PM
20m
Contributed talk

### Speaker

Alexander Clifton (IBS DIMAG)

### Description

A graph is reconstructible if it can be uniquely determined, up to isomorphism, by its multiset of vertex-deleted subgraphs. The Reconstruction Conjecture of Kelly and Ulam states that every graph on $n\geq{3}$ vertices is reconstructible. Ramachandran and Monikandan showed that the Reconstruction Conjecture holds as long as every $2$-connected graph $G$ satisfying either $diam(G)=2$ or $diam(G)=diam(\bar{G})=3$ is reconstructible. Building on their work, we establish that all triangle-free graphs in the following families are reconstructible:

• Graphs with connectivity $3$ and diameter $2$.
• $2$-connected graphs $G$ with $diam(G)=diam(\bar{G})=3$.

We also establish slightly stronger results for the related Edge Reconstruction Conjecture.

### Primary authors

Alexander Clifton (IBS DIMAG) Xiaonan Liu (Georgia Institute of Technology) Reem Mahmoud (Virginia Commonwealth University) Abhinav Shantanam (Simon Fraser University)

### Presentation materials

There are no materials yet.