Seminar: New Variants of the Graph Reconstruction Conjecture

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


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.


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