Size reconstructibility of graphs

MaRDI QIDQ6304856zbMATH OpenFDO

Authors Carla Groenland, Hannah Guggiari, Alex Scott

Publication date 31 July 2018

Abstract: The deck of a graph $G$ is given by the multiset of (unlabelled) subgraphs $G-v:vinV(G)$. The subgraphs $G-v$ are referred to as the cards of $G$. Brown and Fenner recently showed that, for $ngeq29$, 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 $frac120sqrtn$ cards.

This page was built for publication: Size reconstructibility of graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6304856)