BROWSE

Related Scientist

Alexander, Clifton's photo.

Alexander, Clifton
이산수학 그룹
more info

ITEM VIEW & DOWNLOAD

Reconstruction and edge reconstruction of triangle-free graphs

Cited 0 time in webofscience Cited 0 time in scopus
82 Viewed 0 Downloaded
Title
Reconstruction and edge reconstruction of triangle-free graphs
Author(s)
Clifton, Alexander; Liu, Xiaonan; Mahmoud, Reem; Shantanam, Abhinav
Publication Date
2024-02
Journal
Discrete Mathematics, v.347, no.2
Publisher
Elsevier B.V.
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∈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. © 2023 Elsevier B.V.
URI
https://pr.ibs.re.kr/handle/8788114/14627
DOI
10.1016/j.disc.2023.113753
ISSN
0012-365X
Appears in Collections:
Pioneer Research Center for Mathematical and Computational Sciences(수리 및 계산과학 연구단) > Discrete Mathematics Group(이산 수학 그룹) > 1. Journal Papers (저널논문)
Files in This Item:
There are no files associated with this item.

qrcode

  • facebook

    twitter

  • Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.
해당 아이템을 이메일로 공유하기 원하시면 인증을 거치시기 바랍니다.

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.

Browse