Size reconstructibility of graphs

Groenland, C
Guggiari, H
Scott, A

5 August 2020

Journal:

Journal of Graph Theory

Last Updated:

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

2

96

DOI:

10.1002/jgt.22616

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.

905470

Submitted

Journal Article