Journal title
Journal of Graph Theory
Last updated
2024-04-22T11:01:31.257+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.
$\{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
On
Favourite
Off
Publication type
Journal Article