On reconstruction of graphs from the multiset of subgraphs obtained by deleting ℓ\ell vertices

preprint2020arXivOpen access

Abstract

The Reconstruction Conjecture of Ulam asserts that, for n≥3n\geq 3, every nn-vertex graph is determined by the multiset of its induced subgraphs with n−1n-1 vertices. The conjecture is known to hold for various special classes of graphs but remains wide open. We survey results on the more general conjecture by Kelly from 1957 that for every positive integer ℓ\ell there exists MℓM_\ell (with M1=3M_1=3) such that when n≥Mℓn\geq M_\ell every nn-vertex graph is determined by the multiset of its induced subgraphs with n−ℓn-\ell vertices.

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.