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.

 

Graduate Program Seminar Announcement

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

New Variants of the Graph Reconstruction Conjecture

Department of Computer Science
Thursday, May 8, 2014, 2:00 p.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. Given a graph G, three equivalence relations are considered on V(G): card equivalence, automorphism equivalence, and the equivalence of having the same behavior. These relations are analyzed on various example graphs inspired by appropriate flowchart schemes. A structural characterization of card equivalence in terms of automorphism equivalence is emphasized. Relative degree sequence of induced subgraphs of a G is formulated and a new conjecture stating reconstruction of G from the multiset of relative degree-sequences of its induced subgraphs is derived. Eventually it is represented that graphs which have deck without duplicate cards are finally reconstructible. *Keywords*: graph reconstruction, card equivalence, automorphism equivalence, relative degree sequences.