Seminar: New Variants of the Graph Reconstruction Conjecture

Thesis Proposal Presentation

Amitesh Saha Shuva
M.Sc. Candidate
Supervisor: Dr. Miklós Bartha

New Variants of the Graph Reconstruction Conjecture

Department of Computer Science
Friday, November 22, 2013, 11:20a.m., Room EN 2022


One of the most well known unsolved problems of graph theory involves whether a graph can be reconstructed up to isomorphism when all of its vertex-deleted subgraphs are known up to isomorphism. The vertex reconstruction conjecture states that, every graph with at least three vertices is reconstructible. Our research approach will emphasize on establishing that the relative degree sequence generated by the induced subgraphs of a graph, uniquely determines the main graph. There will always be a combination of the degree sequences for which that particular graph
will be distinctive from other graphs. We also draw importance to the fact that the relative degree sequence of induced subgraphs of a graph implies the reconstruction conjecture for that graph. We will try to provide an algorithm that determines the verification of reconstruction conjecture implying relative degree sequence of a graph.



Department of Computer Science

230 Elizabeth Ave, St. John's, NL, CANADA, A1B 3X9

Postal Address: P.O. Box 4200, St. John's, NL, CANADA, A1C 5S7

Tel: (709) 864-8000