TY - JOUR
T1 - Degree Lists and Connectedness are 3-Reconstructible for Graphs with At Least Seven Vertices
AU - Kostochka, Alexandr V.
AU - Nahvi, Mina
AU - West, Douglas B.
AU - Zirlin, Dara
N1 - Funding Information:
A. V. Kostochka: Research supported in part by NSF grant DMS-1600592 and grants 18-01-00353A and 19-01-00682 of the Russian Foundation for Basic Research. D. B. West: Research supported by National Natural Science Foundation of China grants NNSFC 11871439 and 11971439. D. Zirlin: Research supported in part by Arnold O. Beckman Campus Research Board Award RB20003 of the University of Illinois at Urbana-Champaign
Publisher Copyright:
© 2020, Springer Japan KK, part of Springer Nature.
PY - 2020/5
Y1 - 2020/5
N2 - 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≥ 7 , and the threshold on n is sharp. Using this result, we show that when n≥ 7 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≥ 6 , which are also sharp.
AB - 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≥ 7 , and the threshold on n is sharp. Using this result, we show that when n≥ 7 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≥ 6 , which are also sharp.
KW - Connected
KW - Deck
KW - Graph reconstruction
KW - Reconstructibility
UR - http://www.scopus.com/inward/record.url?scp=85078933985&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85078933985&partnerID=8YFLogxK
U2 - 10.1007/s00373-020-02131-6
DO - 10.1007/s00373-020-02131-6
M3 - Article
AN - SCOPUS:85078933985
SN - 0911-0119
VL - 36
SP - 491
EP - 501
JO - Graphs and Combinatorics
JF - Graphs and Combinatorics
IS - 3
ER -