Reconstruction and edge reconstruction of triangle-free graphs

DOI10.1016/J.DISC.2023.113753MaRDI QIDQ6184530FDOQ6184530

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

Publication date 25 January 2024

Published in Discrete Mathematics (Search for Journal in Brave)

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

structural graph theory reconstruction conjecture edge reconstruction conjecture edge-deck

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

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 i n V (G)

. Let

d i a m (G)

and

k a p p a (G)

denote the diameter and the connectivity of a graph

G

, respectively, and let

m a t h c a l G_{2} := G : e x t r m d i a m (G) = 2

and

m a t h c a l G_{3} := G : e x t r m d i a m (G) = e x t r m d i a m (o v e r l i n e G) = 3

. It is known that the Reconstruction Conjecture is true if and only if it is true for every 2-connected graph in

m a t h c a l G_{2} c u p m a t h c a l G_{3}

. Balakumar and Monikandan showed that the Reconstruction Conjecture holds for every triangle-free graph

G

in

m a t h c a l G_{2} c u p m a t h c a l G_{3}

with

k a p p a (G) = 2

. Moreover, they asked whether the result still holds if

k a p p a (G) g e 3

. (If yes, the class of graphs critical for solving the Reconstruction Conjecture is restricted to 2-connected graphs in

m a t h c a l G_{2} c u p m a t h c a l 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

m a t h c a l G_{3}

and every triangle-free graph

G

in

m a t h c a l G_{2}

with

k a p p a (G) = 3

. We also prove similar results about the Edge Reconstruction Conjecture.

Recommendations

Cites work

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)