Research Article
The Reconstruction Conjecture
561 downloads
@INPROCEEDINGS{10.1007/978-3-642-27317-9_3, author={Subhashis Banerjee and Debajit SenSarma and Krishnendu Basuli and Saptarshi Naskar and Samar Sarma}, title={The Reconstruction Conjecture}, proceedings={Advances in Computer Science and Information Technology. Computer Science and Information Technology. Second International Conference, CCSIT 2012, Bangalore, India, January 2-4, 2012. Proceedings, Part III}, proceedings_a={CCSIT PART III}, year={2012}, month={11}, keywords={Multiset Card Deck Matching Perfect matching K-matching Matching polynomial Tree-Decomposition}, doi={10.1007/978-3-642-27317-9_3} }- Subhashis Banerjee
Debajit SenSarma
Krishnendu Basuli
Saptarshi Naskar
Samar Sarma
Year: 2012
The Reconstruction Conjecture
CCSIT PART III
Springer
DOI: 10.1007/978-3-642-27317-9_3
Abstract
The Reconstruction Conjecture is one of the most engaging problems under the domain of Graph Theory. The conjecture proposes that every graph with at least three vertices can be uniquely reconstructed given the multiset of subgraphs produced by deleting each vertex of the original graph one by one. This conjecture has been proven true for several infinite classes of graphs, but the general case remains unsolved. In this paper we will outline the problem and give a practical method for reconstructing a graph from its node-deleted.
Copyright © 2012–2024 ICST
