# 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

Abstract

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.