The Reconstruction Conjecture

Subhashis Banerjee; Debajit SenSarma; Krishnendu Basuli; Saptarshi Naskar; Samar Sarma

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

Research Article

The Reconstruction Conjecture

Download

375 downloads

Cite: BibTeX Plain Text

@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

Subhashis Banerjee¹^,*, Debajit SenSarma¹^,*, Krishnendu Basuli¹^,*, Saptarshi Naskar²^,*, Samar Sarma³^,*

1: West Bengal State University
2: Sarsuna College
3: University Of Calcutta

*Contact email: mail.sb88@gmail.com, debajit.sensarma2008@gmail.com, krishnendu.basuli@gmail.com, sapgrin@gmail.com, sssarma2001@yahoo.com

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.

Keywords: Multiset Card Deck Matching Perfect matching K-matching Matching polynomial Tree-Decomposition

Published: 2012-11-09

: http://dx.doi.org/10.1007/978-3-642-27317-9_3