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)
