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

Reconstruction and Edge Reconstruction of Triangle-free Graphs

Sep 30, 2022, 4:45 PM
Contributed talk Session 2


Alexander Clifton (IBS DIMAG)


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.