Reconstruction and edge reconstruction of triangle-free graphs
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Clifton, Alexander | - |
dc.contributor.author | Liu, Xiaonan | - |
dc.contributor.author | Mahmoud, Reem | - |
dc.contributor.author | Shantanam, Abhinav | - |
dc.date.accessioned | 2024-01-16T22:00:17Z | - |
dc.date.available | 2024-01-16T22:00:17Z | - |
dc.date.created | 2023-10-30 | - |
dc.date.issued | 2024-02 | - |
dc.identifier.issn | 0012-365X | - |
dc.identifier.uri | https://pr.ibs.re.kr/handle/8788114/14627 | - |
dc.description.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. | - |
dc.language | 영어 | - |
dc.publisher | Elsevier B.V. | - |
dc.title | Reconstruction and edge reconstruction of triangle-free graphs | - |
dc.type | Article | - |
dc.type.rims | ART | - |
dc.identifier.wosid | 001096715400001 | - |
dc.identifier.scopusid | 2-s2.0-85174356441 | - |
dc.identifier.rimsid | 82020 | - |
dc.contributor.affiliatedAuthor | Clifton, Alexander | - |
dc.identifier.doi | 10.1016/j.disc.2023.113753 | - |
dc.identifier.bibliographicCitation | Discrete Mathematics, v.347, no.2 | - |
dc.relation.isPartOf | Discrete Mathematics | - |
dc.citation.title | Discrete Mathematics | - |
dc.citation.volume | 347 | - |
dc.citation.number | 2 | - |
dc.type.docType | Article | - |
dc.description.journalClass | 1 | - |
dc.description.journalClass | 1 | - |
dc.description.isOpenAccess | N | - |
dc.description.journalRegisteredClass | scopus | - |
dc.relation.journalResearchArea | Mathematics | - |
dc.relation.journalWebOfScienceCategory | Mathematics | - |
dc.subject.keywordAuthor | Edge reconstruction conjecture | - |
dc.subject.keywordAuthor | Edge-deck | - |
dc.subject.keywordAuthor | Reconstruction conjecture | - |
dc.subject.keywordAuthor | Structural graph theory | - |