Reconstructing the degree sequence of a sparse graph from a partial deck

Abstract

The deck of a graph G is the multiset of cards {G−v:v∈V(G)}. Myrvold (1992) showed that the degree sequence of a graph on n≥7 vertices can be reconstructed from any deck missing one card. We prove that the degree sequence of a graph with average degree d can be reconstructed from any deck missing O(n/d³) cards. In particular, in the case of graphs that can be embedded on a fixed surface (e.g. planar graphs), the degree sequence can be reconstructed even when a linear number of the cards are missing.