Reconstruction and Edge Reconstruction of Triangle-free Graphs

Abstract

The Reconstruction Conjecture due to Kelly and Ulam states that every graph with at least 3 vertices is uniquely determined by its multiset of subgraphs $\{G-v:v\in V(G)\}$. Let $diam(G)$ and $\kappa (G)$ denote the diameter and the connectivity of a graph $G$, respectively, and let ${\mathcal{G}}_2:=\{G:\text{diam}(G)=2\}$ and ${\mathcal{G}}_3:=\{G:\text{diam}(G)=\text{diam}(\overline{G})=3\}$. It is known that the Reconstruction Conjecture is true if and only if it is true for every 2-connected graph in ${\mathcal{G}}_2\cup {\mathcal{G}}_3$. Balakumar and Monikandan showed that the Reconstruction Conjecture holds for every triangle-free graph $G$ in ${\mathcal{G}}_2\cup {\mathcal{G}}_3$ with $\kappa (G)=2$. Moreover, they asked whether the result still holds if $\kappa (G)\ge 3$. (If yes, the class of graphs critical for solving the Reconstruction Conjecture is restricted to 2-connected graphs in ${\mathcal{G}}_2\cup {\mathcal{G}}_3$ which contain triangles.) In this paper, we give a partial solution to their question by showing that the Reconstruction Conjecture holds for every triangle-free graph $G$ in ${\mathcal{G}}_3$ and every triangle-free graph $G$ in ${\mathcal{G}}_2$ with $\kappa (G)=3$. We also prove similar results about the Edge Reconstruction Conjecture.

11 pages, 3 figures