Graph Reconstruction under Godsil–McKay Switching Binary Kernels, Incidence Tensors and Unrooted Completion Rigidity
The vertex deck of a finite simple graph is the multiset of its unlabelled vertex deletions.For the adjacency matrix and the adjacency matrix plus the identity over the two-elementfield, we recover the numbers of null vectors of each support size and the sizes of classes ofvertices with identical nonzero coordinate functionals on the nullspace. These data yieldsufficient reconstruction criteria without degree separation. For four-vertex Godsil–McKayswitching, a transformation preserving the adjacency spectrum, we prove walk and signedsubgraph obstructions and classify 1,172,556 balanced assignments on a fixed ten-vertexcore, excluding all as reconstruction counterexamples. An explicit switching constructionshows that uniqueness of completion with a distinguished added vertex can fail even withexact deck information. An automorphism-normalised counting identity characterises deckequality using unrooted parent completions; finite experiments establish strict gains fromintersecting their candidate classes. Universal switching reconstruction remains open.
Authors
- Tony Newton (ORCID: https://orcid.org/0009-0009-9189-6431)
Publication Details
- Journal
- Zenodo (CERN European Organization for Nuclear Research)
- Published
- 2026-11-21
- DOI
- https://doi.org/10.5281/zenodo.24418658
- Primary Topic
- Graph theory and applications
- Type
- preprint