Reconstruction and edge reconstruction of triangle-free graphs

DOI10.1016/J.DISC.2023.113753MaRDI QIDQ6184530zbMATH OpenFDO

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

edge reconstruction conjecture edge-deck reconstruction conjecture structural graph theory

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.

Review text

For a vertex \(v\) of a graph \(G=(V,E)\), the graph \(G-v\) produced by the deletion of \(v\) is a card; for an edge \(e\in E\), \(G-e\) is an edge-card; the family \(\mathcal{D}(G)=\{G-v:v\in V\}\) of all cards (respectively, the family \(\mathcal{ED}(G)=\{G-e:e\in E\}\)) of all edge-cards) is the deck (respectively edge-deck). In the traditional reconstruction problem one explores whether \(G\) is uniquely determined by \(\mathcal{D}(G)\); in the edge reconstruction problem, introduced in [\textit{F. Harary}, in: Theory of graphs and its applications. Proceedings of the symposium, Smolenice, Czechoslovakia, June 17--20, 1963. Prague: Publishing House of the Czechoslovak Academy of Sciences. 47--52 (1964; Zbl 0161.43404)], one explores whether \(G\) is uniquely determined by \(\mathcal{ED}(G)\). The connectivity of \(G\), \(\kappa(G)\), is the size of its smallest cut set. \(\mathcal{G}_2\) and \(\mathcal{G}_3\) respectively denote the set of graphs \(G\) of diameter 2, and the set of graphs \(G\) of diameter 3 whose complement \(\overline G\) also has diameter 3; it is known that the reconstruction conjecture can be reduced to its truth for every 2-connected graph in \(\mathcal{G}_2\cup\mathcal{G}_3\) [\textit{S. K. Gupta} et al., Discrete Math. 272, No. 2--3, 291--296 (2003; Zbl 1028.05070)]. In [\textit{S. Monikandan} and \textit{J. Balakumar}, Australas. J. Comb. 53, 141--150 (2012; Zbl 1256.05154)] a problem, Problem C, involving triangle-free graphs \(G\) of connectivity \(\kappa(G)\ge3\) was proposed, of which the present authors observe that one part (involving \(\mathcal{G}_2\)) was confirmed in [\textit{P. Devi Priya} and \textit{S. Monikandan}, Australas. J. Comb. 80, Part 2, 167--177 (2021; Zbl 1468.05134)], and of which the remainder (involving \(\mathcal{G}_3\)) is addressed in the present paper; the present authors also prove similar results about the edge reconstruction conjecture. Caveat lector! There are multiple confusing editorial deficiencies in this paper, in which the name of a concept or pair of concepts being defined is erroneously printed twice, without spacing, in each of two adjacent type-faces.

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)