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

Journal article (2022)

Authors

C.E. Groenland Universiteit Utrecht
Tom Johnston University of Oxford
Andrey Kupavskii Université Grenoble Alpes, Moscow Institute of Physics and Technology
Kitty Meeks University of Glasgow
Alex Scott University of Oxford
Jane Tan University of Oxford
Affiliation
External organisation
Graph reconstruction Reconstruction conjecture Degree sequence K-counts Missing cards Partial deck
More Info
expand_more

Published Date

2022

Language

English

Reuse Rights

Other than for strictly personal use, it is not permitted to download, forward or distribute the text or part of it, without the consent of the author(s) and/or copyright holder(s), unless the work is under an open content license such as Creative Commons.

Affiliation

External organisation

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/d3) 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.