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 -