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: | |
Nepřihlášeným uživatelům se plný text nezobrazuje | K zobrazení výsledku je třeba se přihlásit. |