Abstract
The deck of a graph (Formula presented.) is given by the multiset of (unlabeled) subgraphs (Formula presented.). The subgraphs (Formula presented.) are referred to as the cards of (Formula presented.). Brown and Fenner recently showed that, for (Formula presented.), the number of edges of a graph (Formula presented.) can be computed from any deck missing 2 cards. We show that, for sufficiently large (Formula presented.), the number of edges can be computed from any deck missing at most (Formula presented.) cards.
| Original language | English |
|---|---|
| Article number | 2 |
| Pages (from-to) | 326-337 |
| Number of pages | 12 |
| Journal | Journal of Graph Theory |
| Volume | 96 |
| Issue number | 2 |
| DOIs | |
| Publication status | Published - Feb 2021 |
Bibliographical note
Funding Information:We would like to thank the referees for their helpful comments. Alex Scott was supported by a Leverhulme Trust Research Fellowship. “Open access funding enabled and organized by Projekt DEAL.”
Publisher Copyright:
© 2020 The Authors. Journal of Graph Theory published by Wiley Periodicals LLC
Keywords
- common cards
- graph reconstruction
- partial deck
- size reconstruction
- vertex-deleted subgraphs
Fingerprint
Dive into the research topics of 'Size reconstructibility of graphs'. Together they form a unique fingerprint.Cite this
- APA
- Author
- BIBTEX
- Harvard
- Standard
- RIS
- Vancouver