Size reconstructibility of graphs

Groenland, C.E.; Guggiari, Hannah; Scott, Alex

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

To reference this document use:

http://resolver.tudelft.nl/uuid:7136691e-2bde-49db-86f7-de78f6e656dc

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.

No files available

Metadata only record. There are no files for this journal article.