Degree Lists and Connectedness are 3-Reconstructible for Graphs with At Least Seven Vertices

Autor:	Douglas B. West, Mina Nahvi, Alexandr V. Kostochka, Dara Zirlin
Rok vydání:	2020
Předmět:	Multiset Mathematics::Combinatorics Social connectedness 0211 other engineering and technologies 021107 urban & regional planning 0102 computer and information sciences 02 engineering and technology 01 natural sciences Graph Theoretical Computer Science Combinatorics Computer Science::Discrete Mathematics 010201 computation theory & mathematics Discrete Mathematics and Combinatorics Graph property Mathematics
Zdroj:	Graphs and Combinatorics. 36:491-501
ISSN:	1435-5914 0911-0119
Popis:	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\ge 7$$, and the threshold on n is sharp. Using this result, we show that when $$n\ge 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\ge 6$$, which are also sharp.
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_________::af38e2b12a15e9ea0dee2695ac694353 https://doi.org/10.1007/s00373-020-02131-6 Zobrazit plný text záznamu Plný text ve formátu PDF Plný text ve formátu HTML
Nepřihlášeným uživatelům se plný text nezobrazuje	K zobrazení výsledku je třeba se přihlásit.