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

None, None; None, None; None, None; None, None; None, None; None, None

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

Journal Article (2022)

Author(s)

Carla Groenland (Universiteit Utrecht)

Tom Johnston (University of Oxford)

Andrey Kupavskii (Moscow Institute of Physics and Technology, Université Grenoble Alpes)

Kitty Meeks (University of Glasgow)

Alex Scott (University of Oxford)

Jane Tan (University of Oxford)

Graph reconstruction Reconstruction conjecture Degree sequence K-counts Missing cards Partial deck

DOI related publication

https://doi.org/10.1016/j.jctb.2022.07.004 Final published version

To reference this document use

https://resolver.tudelft.nl/uuid:56bb6747-c48c-47f2-9b59-9c7a4c0440ff

More Info

expand_more

Publication Year

2022

Language

English

Journal title

Journal of Combinatorial Theory. Series B

Volume number

157

Pages (from-to)

283-293

Downloads counter

222

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.