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 non-isomorphic graphs produced by GM switching cannot form counterexamples to the Reconstruction Conjecture. The general assertion remains an open target in this note.
Abstract
We study whether Godsil-McKay switching can produce graphs that are simultaneously non-isomorphic and deck-equivalent. A crucial correction is that GM switching can never alter the total number of triangles, since that number is determined by the adjacency spectrum. The useful statistic is instead the distribution of triangles among the vertex-deleted cards.
For standard one-cell switching, the note derives exact degree and local-triangle formulas and gives deck-separation criteria using degree–triangle signatures, neighbour-degree profiles, common-neighbour counts, deleted characteristic polynomials, and proper-subgraph counts such as K4. It also proves that no non-isomorphic regular GM pair can have equal decks. These are partial results; the universal GM-deck assertion remains open.
Key Partial Theorem
Partial results. A non-isomorphic one-cell GM pair has different decks whenever its degree multiset, degree–triangle card signature, reconstructible common-neighbour distribution, or a proper-subgraph/card profile differs. Every regular graph is reconstructible, so regular GM pairs are also excluded. Exact small-order searches and worked examples show where the successive criteria succeed and where simpler tests fail.
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).