We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
Reconstruction from the deck of k‐vertex induced subgraphs.
- Authors
Spinoza, Hannah; West, Douglas B
- Abstract
The k‐ deck of a graph is its multiset of subgraphs induced by k vertices; we study what can be deduced about a graph from its k‐deck. We strengthen a result of Manvel by proving for ℓ∈N that when n is large enough (n>2ℓ(ℓ+1)2 suffices), the (n−ℓ)‐deck determines whether an n‐vertex graph is connected (n≥25 suffices when ℓ=3, and n≤2l cannot suffice). The reconstructibilityρ(G) of a graph G with n vertices is the largest ℓ such that G is determined by its (n−ℓ)‐deck. We generalize a result of Bollobás by showing ρ(G)≥(1−o(1))n∕2 for almost all graphs. As an upper bound on minρ(G), we have ρ(Cn)=⌈n∕2⌉=ρ(Pn)+1. More generally, we compute ρ(G) whenever Δ(G)=2, which involves extending a result of Stanley. Finally, we show that a complete r‐partite graph is reconstructible from its (r+1)‐deck.
- Subjects
SUBGRAPHS; GEOMETRIC vertices; RECONSTRUCTION (Graph theory); RANDOM graphs; GRAPH theory
- Publication
Journal of Graph Theory, 2019, Vol 90, Issue 4, p497
- ISSN
0364-9024
- Publication type
Article
- DOI
10.1002/jgt.22409