Seminar: New Variants of the Graph Reconstruction Conjecture
Graduate Program Seminar Announcement
Amitesh Saha Shuva
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
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.