Reconstruction and edge reconstruction of triangle-free graphs

DOI10.1016/J.DISC.2023.113753arXiv2210.00338MaRDI QIDQ6184530FDOQ6184530

Authors: Alexander Clifton, Xiaonan Liu, Reem Mahmoud, Abhinav Shantanam 

Publication date: 25 January 2024

Published in: Discrete Mathematics (Search for Journal in Brave)

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:vinV(G)$. Let $diam(G)$ and $kappa(G)$ denote the diameter and the connectivity of a graph $G$, respectively, and let $mathcal{G}_2:=G:extrmdiam(G)=2$ and $mathcal{G}_3:=G:extrmdiam(G)=extrmdiam(overlineG)=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}cupmathcal{G}_3$. Balakumar and Monikandan showed that the Reconstruction Conjecture holds for every triangle-free graph $G$ in $mathcal{G}_{2}cupmathcal{G}_3$ with $kappa(G)=2$. Moreover, they asked whether the result still holds if $kappa(G)ge3$. (If yes, the class of graphs critical for solving the Reconstruction Conjecture is restricted to 2-connected graphs in $mathcal{G}_{2}cupmathcal{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.

Full work available at URL: https://arxiv.org/abs/2210.00338

Recommendations

• scientific article
• scientific article; zbMATH DE number 3080938
• scientific article; zbMATH DE number 3407754
• Eine Bemerkung zum Satz von Vitali über Konvergenz von Funktionenfolgen: Dem stets hilftsbereiten Herrn Kollegen H. L. Schmid, gewidmet
• scientific article; zbMATH DE number 1839786
• Holomorphic mappings of complex manifolds
• scientific article; zbMATH DE number 5593209
• On \(\varepsilon\)-representations
• scientific article

zbMATH Keywords

structural graph theoryreconstruction conjectureedge reconstruction conjectureedge-deck

Mathematics Subject Classification ID

Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Structural characterization of families of graphs (05C75)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Graph reconstruction—a survey
• A congruence theorem for trees
• Title not available (Why is that?)
• Title not available (Why is that?)
• On the edge-reconstruction number of disconnected graphs
• Reconstructing Graphs
• The reconstruction conjecture is true if all 2-connected graphs are reconstructible
• Some work towards the proof of the reconstruction conjecture
• Reconstruction of bipartite graphs and triangle-free graphs with connectivity two
• Graph reconstruction conjecture: reductions using complement, connectivity and distance
• Title not available (Why is that?)

This page was built for publication: Reconstruction and edge reconstruction of triangle-free graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6184530)