Degree lists and connectedness are 3-reconstructible for graphs with at least seven vertices
classification
🧮 math.CO
keywords
graphreconstructibledeckdegreesharpverticeswhenconnectedness
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.