TY - JOUR
T1 - Reconstruction and edge reconstruction of triangle-free graphs
AU - Clifton, Alexander
AU - Liu, Xiaonan
AU - Mahmoud, Reem
AU - Shantanam, Abhinav
N1 - Publisher Copyright:
© 2023 Elsevier B.V.
PY - 2024/2
Y1 - 2024/2
N2 - 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:diam(G)=2} and G3:={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 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∪G3 which contain triangles.) The case when G∈G3 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 G2 with κ(G)=3. We also prove similar results about the Edge Reconstruction Conjecture.
AB - 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:diam(G)=2} and G3:={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 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∪G3 which contain triangles.) The case when G∈G3 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 G2 with κ(G)=3. We also prove similar results about the Edge Reconstruction Conjecture.
KW - Edge reconstruction conjecture
KW - Edge-deck
KW - Reconstruction conjecture
KW - Structural graph theory
UR - http://www.scopus.com/inward/record.url?scp=85174356441&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85174356441&partnerID=8YFLogxK
U2 - 10.1016/j.disc.2023.113753
DO - 10.1016/j.disc.2023.113753
M3 - Article
AN - SCOPUS:85174356441
SN - 0012-365X
VL - 347
JO - Discrete Mathematics
JF - Discrete Mathematics
IS - 2
M1 - 113753
ER -