Reconstructing the degree sequence of a sparse graph from a partial deck
Publication date
2022-11
Authors
Groenland, Carla
Johnston, Tom
Kupavskii, Andrey
Meeks, Kitty
Scott, Alex
Tan, Jane
Editors
Advisors
Supervisors
Document Type
Article
Metadata
Show full item recordCollections
License
cc_by
Abstract
The deck of a graph G is the multiset of cards. Myrvold (1992) showed that the degree sequence of a graph on 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 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.
Keywords
Graph reconstruction, Degree sequence, Kt-counts, Partial deck, Reconstruction conjecture
Citation
Groenland, C, Johnston, T, Kupavskii, A, Meeks, K, Scott, A & Tan, J 2022, 'Reconstructing the degree sequence of a sparse graph from a partial deck', Journal of Combinatorial Theory, Series B, vol. 157, pp. 283-293. https://doi.org/10.1016/j.jctb.2022.07.004