The Library
An algebraic formulation of the graph reconstruction conjecture
Tools
Oliveira, Igor Carboni and Thatte, Bhalchandra D. (2015) An algebraic formulation of the graph reconstruction conjecture. Journal of Graph Theory, 81 (4). pp. 351-363. doi:10.1002/jgt.21880 ISSN 0364-9024.
|
PDF
WRAP-algebraic-formulation-graph-reconstruction-conjecture-Oliveira-2015.pdf - Accepted Version - Requires a PDF viewer. Download (935Kb) | Preview |
Official URL: http://dx.doi.org/10.1002/jgt.21880
Abstract
The graph reconstruction conjecture asserts that every finite simple graph on at least three vertices can be reconstructed up to isomorphism from its deck - the collection of its vertex-deleted subgraphs. Kocay’s Lemma is an important tool in graph reconstruction. Roughly speaking, given the deck of a graph G and any finite sequence of graphs, it gives a linear constraint that every reconstruction of G must satisfy. Let ψ(n) be the number of distinct (mutually non-isomorphic) graphs on n vertices, and let d(n) be the number of distinct decks that can be constructed from these graphs. Then the difference ψ(n)−d(n) measures how many graphs cannot be reconstructed from their decks. In particular, the graph reconstruction conjecture is true for n-vertex graphs if and only if ψ(n) = d(n). We give a framework based on Kocay’s lemma to study this discrepancy. We prove that if M is a matrix of covering numbers of graphs by sequences of graphs, then d(n) ≥ rankR(M). In particular, all n-vertex graphs are reconstructible if one such matrix has rank ψ(n). To complement this result, we prove that it is possible to choose a family of sequences of graphs such that the corresponding matrix M of covering numbers satisfies d(n) = rankR(M).
Item Type: | Journal Article | |||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics | |||||||||||||||
Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | |||||||||||||||
Library of Congress Subject Headings (LCSH): | Reconstruction (Graph theory), Algebra -- Graphic methods, Isomorphisms (Mathematics) | |||||||||||||||
Journal or Publication Title: | Journal of Graph Theory | |||||||||||||||
Publisher: | John Wiley & Sons Ltd. | |||||||||||||||
ISSN: | 0364-9024 | |||||||||||||||
Official Date: | April 2015 | |||||||||||||||
Dates: |
|
|||||||||||||||
Volume: | 81 | |||||||||||||||
Number: | 4 | |||||||||||||||
Page Range: | pp. 351-363 | |||||||||||||||
DOI: | 10.1002/jgt.21880 | |||||||||||||||
Status: | Peer Reviewed | |||||||||||||||
Publication Status: | Published | |||||||||||||||
Reuse Statement (publisher, data, author rights): | This is the peer reviewed version of the following article: Oliveira, I. C. and Thatte, B. D. (2016), An Algebraic Formulation of the Graph Reconstruction Conjecture. J. Graph Theory, 81: 351-363. doi:10.1002/jgt.21880, which has been published in final form at https://doi.org/10.1002/jgt.21880. This article may be used for non-commercial purposes in accordance with Wiley Terms and Conditions for Use of Self-Archived Versions. | |||||||||||||||
Access rights to Published version: | Restricted or Subscription Access | |||||||||||||||
Date of first compliant deposit: | 7 November 2019 | |||||||||||||||
Date of first compliant Open Access: | 7 November 2019 | |||||||||||||||
RIOXX Funder/Project Grant: |
|
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |
Downloads
Downloads per month over past year