pith. sign in

arxiv: 1904.11901 · v1 · pith:FUKCPENCnew · submitted 2019-04-26 · 🧮 math.CO

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

classification 🧮 math.CO
keywords graphreconstructibledeckdegreesharpverticeswhenconnectedness
0
0 comments X
read the original 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.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.