## 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∈V(G)}. Let diam(G) and κ(G) denote the diameter and the connectivity of a graph G, respectively, and let G_{2}:={G:diam(G)=2} and G_{3}:={G:diam(G)=diam(G‾)=3}. It is known that the Reconstruction Conjecture is true if and only if it is true for every 2-connected graph in G_{2}∪G_{3}. Balakumar and Monikandan showed that the Reconstruction Conjecture holds for every triangle-free graph G in G_{2}∪G_{3} with κ(G)=2. Moreover, they asked whether the result still holds if κ(G)≥3. (If yes, the class of graphs critical for solving the Reconstruction Conjecture is restricted to 2-connected graphs in G_{2}∪G_{3} which contain triangles.) The case when G∈G_{3} and κ(G)≥3 was recently confirmed by Devi Priya and Monikandan. In this paper, we further show the Reconstruction Conjecture holds for every triangle-free graph G in G_{2} with κ(G)=3. We also prove similar results about the Edge Reconstruction Conjecture.

Original language | English (US) |
---|---|

Article number | 113753 |

Journal | Discrete Mathematics |

Volume | 347 |

Issue number | 2 |

DOIs | |

State | Published - Feb 2024 |

## Keywords

- Edge reconstruction conjecture
- Edge-deck
- Reconstruction conjecture
- Structural graph theory

## ASJC Scopus subject areas

- Theoretical Computer Science
- Discrete Mathematics and Combinatorics