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

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
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
NOV
preprint

Graph Reconstruction under Godsil–McKay Switching Binary Kernels, Incidence Tensors and Unrooted Completion Rigidity

Tony Newton
Zenodo (CERN European Organization for Nuclear Research)
Graph theory and applications
preprint

Graph Reconstruction under Godsil–McKay Switching Binary Kernels, Incidence Tensors and Unrooted Completion Rigidity

Tony Newton
preprint en

Abstract

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.

Zenodo (CERN European Organization for Nuclear Research)
Graph theory and applications
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

Laika access coming soon
Graph Reconstruction under Godsil–McKay Switching Binary Kernels, Incidence Tensors and Unrooted Completion Rigidity — Tony Newton · Zenodo (CERN European Organization for Nuclear Research) (2026) | TGRS Research Map | TGRS