Size reconstructibility of graphs
Publication date
2021-02
Authors
Groenland, Carla
Guggiari, Hannah
Scott, Alex
Editors
Advisors
Supervisors
Document Type
Article
Metadata
Show full item recordCollections
License
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.
Keywords
common cards, graph reconstruction, partial deck, size reconstruction, vertex-deleted subgraphs, Geometry and Topology
Citation
Groenland, C, Guggiari, H & Scott, A 2021, 'Size reconstructibility of graphs', Journal of Graph Theory, vol. 96, no. 2, 2, pp. 326-337. https://doi.org/10.1002/jgt.22616