Size reconstructibility of graphs

Author: 

Groenland, C
Guggiari, H
Scott, A

Journal: 

Journal of Graph Theory

Last Updated: 

2020-10-12T22:02:01.287+01:00

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