Introduction
The Reconstruction Conjecture (RC), proposed in 1941, remains one of the most significant open problems in graph theory. It posits that any finite graph with at least three vertices can be uniquely reconstructed from its "deck"—the collection of all vertex-deleted subgraphs. This paper focuses on "weak reconstruction" within the class of Self-Complementary (SC) graphs. A graph is self-complementary if it is isomorphic to its own complement. Weak reconstruction asks: if we know a graph belongs to the SC class, can we uniquely identify it from its deck among all other SC graphs?
Methodology
The researchers at IIT Delhi developed an exhaustive computational framework to verify weak reconstruction for SC graphs. The process is divided into two primary steps: identifying the graphs within the class and performing pairwise comparisons of their decks to ensure no two distinct graphs share the same deck.
To handle the massive number of SC graphs, which grows more than exponentially with the number of vertices, the authors implemented a multi-level pruning strategy:
- Level-1 Pruning (Inter-graph): Graphs are partitioned into groups based on invariants like degree sequence, characteristic polynomial, and diameter. Comparisons are only performed within these groups.
- Level-2 Pruning (Intra-deck): Before full isomorphism checks, the degree sequences of subgraphs within the decks are compared. If they do not match, the decks are immediately flagged as different.
- Isomorphism Checking: The
nautylibrary is used for the final, computationally intensive isomorphism tests.
Computational Efficiency and Pruning
The effectiveness of the pruning strategy is critical for feasibility. As shown in the comparison of graph pairs, Level-1 pruning dramatically reduces the number of required isomorphism checks by grouping graphs with identical invariants.
By using "cheap" calculations like degree sequences to avoid "expensive" isomorphism checks, the researchers were able to extend the verification to $n=17$ vertices. At $n=17$, there are over 11 million SC graphs, making exhaustive search without pruning computationally prohibitive.
Results and Discussion
The study successfully verified that weak reconstruction holds for all SC graphs up to 17 vertices. No counter-examples were found. Additionally, the authors provided an enumeration of SC graphs for vertex counts up to 101, highlighting the extreme scale of the problem; for $n=101$, the number of SC graphs is represented by a 344-digit number.
While weak reconstruction is a vital step, full proof of the RC for SC graphs also requires proving "recognizability"—the ability to determine if a given deck belongs to an SC graph without prior knowledge. Future research should focus on this aspect to bridge the gap between weak and strong reconstruction.
Summary updated