The size of a graph is reconstructible from any n - 2 cards
- Submitting institution
-
Birkbeck College
- Unit of assessment
- 11 - Computer Science and Informatics
- Output identifier
- 158
- Type
- D - Journal article
- DOI
-
10.1016/j.disc.2017.08.026
- Title of journal
- Discrete Mathematics
- Article number
- -
- First page
- 165
- Volume
- 341
- Issue
- 1
- ISSN
- 0012-365X
- Open access status
- Compliant
- Month of publication
- September
- Year of publication
- 2017
- URL
-
http://eprints.bbk.ac.uk/id/eprint/19609/
- Supplementary information
-
-
- Request cross-referral to
- -
- Output has been delayed by COVID-19
- No
- COVID-19 affected output statement
- -
- Forensic science
- No
- Criminology
- No
- Interdisciplinary
- No
- Number of additional authors
-
1
- Research group(s)
-
1 - Algorithms, Verification and Software
- Citation count
- 1
- Proposed double-weighted
- No
- Reserve for an output with double weighting
- No
- Additional information
- The result proved in this paper is the first improvement since Myrvold proved the corresponding result for n-1 cards (single-vertex-deleted subgraphs) over 25 years ago. This result is related to the famous Graph Reconstruction Conjecture proposed by Kelly and Ulam more than 75 years ago, which is still open. Although there has been some progress with the Reconstruction Conjecture and related open problems over the intervening years, there have been no major breakthroughs. Even the apparently relatively “simple” problem of size reconstruction considered in this paper has proved difficult to attack, so even a modest improvement is significant.
- Author contribution statement
- -
- Non-English
- No
- English abstract
- -