Reconstruction from the deck of k ‐vertex induced subgraphs

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 ) 2suffices), the ( n − ℓ ) ‐deck determines whether an n ‐vertex graph is connected ( n ≥ 25 suffices when ℓ = 3 , and n ≤ 2 l 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 ρ ( C n ) = ⌈ n ∕ 2 ⌉ = ρ ( P n ) + 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.