Exhaustive Verification of Weak Reconstruction For Self Complementary Graphs

S. K. Gupta, Akash Khandelwal, Apurv Tiwari, SrilekhaarXiv 2010 · arXiv

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.

Flowchart of the two-step verification process for weak reconstruction.

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:

  1. 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.
  2. 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.
  3. Isomorphism Checking: The nauty library 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.

Comparison of total graph pairs versus reduced pairs after Level-1 pruning.

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

Abstract

This paper presents an exhaustive approach for verification of the weak reconstruction of Self Complementary Graphs up to 17 vertices. It describes the general problem of the Reconstruction Conjecture, explaining the complexity involved in checking deck-isomorphism between two graphs. In order to improve the computation time, various pruning techniques have been employed to reduce the number of graph-isomorphism comparisons. These techniques offer great help in proceeding with a reconstructive approach. An analysis of the numbers involved is provided, along with the various limitations of this approach. A list enumerating the number of SC graphs up till 101 vertices is also appended.
BibTeX
@misc{gupta2010exhaustive,
  author = {S. K. Gupta and Sahil Singla and Akash Khandelwal and Apurv Tiwari and Srilekha},
  title = {{Exhaustive Verification of Weak Reconstruction For Self Complementary Graphs}},
  year = {2010},
  eprint = {1012.5995},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1012.5995},
}
Figure