Pith. sign in

REVIEW

Degree lists and connectedness are $3$-reconstructible for graphs with at least seven vertices

Not yet reviewed by Pith; the record is open.

This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.

SPECIMEN: schema-true, not a live event

T0 review · schema-true

One-sentence machine reading of the paper's core claim.

pith:XXXXXXXX · record.json · timestamp

arxiv 1904.11901 v1 pith:FUKCPENC submitted 2019-04-26 math.CO

classification math.CO
keywords graphreconstructibledeckdegreesharpverticeswhenconnectedness
verification ladder T0 review T1 audit T2 compute T3 formal
0 comments
abstract

The $k$-deck of a graph is the multiset of its subgraphs induced by $k$ vertices. A graph or graph property is $l$-reconstructible if it is determined by the deck of subgraphs obtained by deleting $l$ vertices. We show that the degree list of an $n$-vertex graph is $3$-reconstructible when $n\ge7$, and the threshold on $n$ is sharp. Using this result, we show that when $n\ge7$ the $(n-3)$-deck also determines whether an $n$-vertex graph is connected; this is also sharp. These results extend the results of Chernyak and Manvel, respectively, that the degree list and connectedness are $2$-reconstructible when $n\ge6$, which are also sharp.

Discussion (0). Continue with ORCID to comment.

Pith tools