Size reconstructibility of graphs

Journal article (2021)

Authors

C.E. Groenland University of Oxford
Hannah Guggiari University of Oxford
Alex Scott University of Oxford
Affiliation
External organisation
Common cards Graph reconstruction Partial deck Size reconstruction Vertex-deleted subgraphs
More Info
expand_more

Published Date

2021

Language

English

Reuse Rights

Other than for strictly personal use, it is not permitted to download, forward or distribute the text or part of it, without the consent of the author(s) and/or copyright holder(s), unless the work is under an open content license such as Creative Commons.

Affiliation

External organisation

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.