Partial Progress on Reconstructability vs. Godsil-McKay Switching
Overview
This working note explores a connection between two foundational problems in graph theory:
- The Reconstruction Conjecture (Kelly-Ulam): every finite simple graph on ≥ 3 vertices is determined up to isomorphism by the multiset of its vertex-deleted subgraphs (the “deck”).
- Godsil-McKay (GM) Switching: a standard construction that produces non-isomorphic graphs with the same spectrum.
The central question:
If GM switching produces two non-isomorphic graphs G and G', must their decks differ?
A positive answer would mean that cospectral, non-isomorphic graphs produced by GM switching are still reconstructible — i.e., GM-cospectral pairs do not form counterexamples to the Reconstruction Conjecture.
Abstract
We study whether Godsil-McKay switching can produce graphs that are simultaneously non-isomorphic and deck-equivalent (thus serving as counterexamples to the reconstruction conjecture). We prove a partial result in a simple GM setting: degree sequences are reconstructible from the deck and are invariant to a specific class of GM switching, so GM-switched pairs of graphs are distinguishable by their decks whenever the switching alters the degree sequence.
We also provide a general criterion — a "card invariant" — that, when it can be verified, rules out deck-equivalence between any GM-switched pair. The full conjecture (that no GM switching can produce deck-equivalent non-isomorphic graphs) remains open.
Key Partial Theorem
Partial Result. Let G and G' be non-isomorphic graphs related by GM switching. If the switching alters the degree sequence of G, then G and G' are distinguishable by their vertex-deleted decks. In particular, they cannot both be counterexamples to the Reconstruction Conjecture via deck-equivalence.
Context
This is a note in active development, emerging from research on spectral graph theory and its connections to combinatorial graph invariants. It complements the work in Graph-Distinguishability—Journal on generalized cospectral mates, and is motivated by the broader question of how much structural information is captured by spectral data versus combinatorial data (the deck).