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

Carla Groenland; Tom Johnston; Andrey Kupavskii; Kitty Meeks; Alex Scott; Jane Tan

doi:10.1016/j.jctb.2022.07.004

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

Carla Groenland, Tom Johnston, Andrey Kupavskii, Kitty Meeks, Alex Scott, Jane Tan

Sub Algorithms and Complexity

Research output: Contribution to journal › Article › Academic › peer-review

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.

Original language	English
Pages (from-to)	283-293
Number of pages	11
Journal	Journal of Combinatorial Theory, Series B
Volume	157
DOIs	https://doi.org/10.1016/j.jctb.2022.07.004
Publication status	Published - Nov 2022

Keywords

Graph reconstruction
Degree sequence
Kt-counts
Partial deck
Reconstruction conjecture

Access to Document

10.1016/j.jctb.2022.07.004Licence: CC BY

1-s2.0-S0095895622000703-mainFinal published version, 318 KBLicence: CC BY

Cite this

@article{79ac7d1476384b5ab0575afb149b0238,

title = "Reconstructing the degree sequence of a sparse graph from a partial deck",

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",

author = "Carla Groenland and Tom Johnston and Andrey Kupavskii and Kitty Meeks and Alex Scott and Jane Tan",

year = "2022",

month = nov,

doi = "10.1016/j.jctb.2022.07.004",

language = "English",

volume = "157",

pages = "283--293",

journal = "Journal of Combinatorial Theory, Series B",

issn = "1096-0902",

publisher = "Academic Press Inc.",

}

TY - JOUR

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

AU - Groenland, Carla

AU - Johnston, Tom

AU - Kupavskii, Andrey

AU - Meeks, Kitty

AU - Scott, Alex

AU - Tan, Jane

PY - 2022/11

Y1 - 2022/11

N2 - 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.

AB - 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.

KW - Graph reconstruction

KW - Degree sequence

KW - Kt-counts

KW - Partial deck

KW - Reconstruction conjecture

UR - https://doi.org/10.1016/j.jctb.2022.07.004

U2 - 10.1016/j.jctb.2022.07.004

DO - 10.1016/j.jctb.2022.07.004

M3 - Article

SN - 1096-0902

VL - 157

SP - 283

EP - 293

JO - Journal of Combinatorial Theory, Series B

JF - Journal of Combinatorial Theory, Series B

ER -

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

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this