Size reconstructibility of graphs

Author: 

Groenland, C
Guggiari, H
Scott, A

Publication Date: 

5 August 2020

Journal: 

Journal of Graph Theory

Last Updated: 

2021-04-05T21:35:14.303+01:00

Issue: 

2

Volume: 

96

DOI: 

10.1002/jgt.22616

page: 

326-337

abstract: 

The deck of a graph $G$ is given by the multiset of (unlabelled) subgraphs
$\{G-v:v\in V(G)\}$. The subgraphs $G-v$ are referred to as the cards of $G$.
Brown and Fenner recently showed that, for $n\geq29$, the number of edges of a
graph $G$ can be computed from any deck missing 2 cards. We show that, for
sufficiently large $n$, the number of edges can be computed from any deck
missing at most $\frac1{20}\sqrt{n}$ cards.

Symplectic id: 

905470

Submitted to ORA: 

Submitted

Publication Type: 

Journal Article