Adjacency-degree algebras and spectral determination of graphs

Abstract

McKay proved that the spectra of all polynomial functions of the adjacency matrix $A$ and the diagonal degree matrix $D$ determine a tree. We prove a principal version of this theorem. Let $\mathcal A(G)=\langle I,A_G,D_G\rangle$ and let $M_G=\mathcal A(G)\mathbf1$ be the cyclic module generated by the all-ones vector. For connected graphs the ideal $\mathcal A(G)J\mathcal A(G)$, where $J=\mathbf1\mathbf1^T$, acts on $M_G$ as the full endomorphism algebra. We show that every forest satisfies $M_G=U_G$, the automorphism-orbit module, and that the induced algebra on the orbit quotient of a tree is a full matrix algebra. It follows that the scalar moments $\mathbf1^Tw(A_T,D_T)\mathbf1$ determine every tree. For general graphs these moments are degree-decorated caterpillar homomorphism counts. The resulting moment-rigidity class lies inside the amenable, compact, refinable hierarchy of color refinement, and its first small-order failures are ten-vertex integral switchings invisible to $M_G$.

Disclosure

“rogram (No. JCYJ20241202130548062), the Natural Science Foundation of Shenzhen (No. JCYJ20230807142703006), and the Key Research Platforms and Projects of the Guangdong Provincial Department of Education (No.2023ZDZX1034). Declaration of generative AI and AI-assisted technologies in the manuscript preparation process During the preparation of this work, the authors used ChatGPT and Codex, for language editing, organization of exposition, proofreading, consistency checks, assistance”

PDF page 16

Classification

Rewriting existing author-written text

Multiplier

4

Verified

2026-08-23T19:04:06.370035Z

Structural counts