2005/03/16 by Dhananjay P. Mehendale, Mehendale, Dhananjay P.
Computer Science · Mathematics · #Computational Geometry and Mesh Generation #Digital Image Processing Techniques #FOS: Mathematics #General Mathematics (math.GM) #Topological and Geometric Data Analysis #math.GM
paper · pdf · doi:10.48550/arxiv.math/0503316
39 pages. Typos corrected. A new Section 17 is added which offers a new smart proof for reconstruction conjecture
openalex publication_date 2005/03/16 · arxiv created 2011/10/20 · arxiv updated 2011/10/21 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In this paper we discuss reconstruction problems for graphs. We develop some new ideas like isomorphic extension of isomorphic graphs, partitioning of vertex sets into sets of equivalent points, subdeck property, etc. and develop an approach to deal with reconstruction problem. We then discuss complete sets of invariants for graphs and reconstruction conjecture. We then begin with development of few equivalent formulations of reconstruction conjecture. In the last section we briefly elaborate the formulation due to Harary its exact demand and finally proceed to give a different proof of reconstruction conjecture using reconstructibility of graph from its spanning trees and reconstructibility of tree from its pendant point deleted deck of subtrees. This last proof can be used to develop a systematic procedure to reconstruct unique graph from its deck.