2022/10/01 by Alexander Clifton, Xiaonan Liu, Clifton, Alexander +5
Computer Science · #05C60 #Advanced Algebra and Logic #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.2210.00338
openalex publication_date 2022/10/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 G2:=\G: \textrmdiam(G)=2\ and G3:=\G:\textrmdiam(G)=\textrmdiam(G)=3\. It is known that the Reconstruction Conjecture is true if and only if it is true for every 2-connected graph in G2∪ G3. Balakumar and Monikandan showed that the Reconstruction Conjecture holds for every triangle-free graph G in G2∪ G3 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 G2\cupG3 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 G3 and every triangle-free graph G in G2 with κ(G)=3. We also prove similar results about the Edge Reconstruction Conjecture.