Primary decomposition theorem and generalized spectral characterization of graphs

2025/04/17 by Songlin Guo, Wei Wang, Guo, Songlin +1 · 1 citation
Mathematics · Computer Science · #Graph theory and applications #Matrix Theory and Algorithms #Tensor decomposition and applications

paper · pdf · doi:10.48550/arxiv.2504.12932

Abstract

Suppose G is a controllable graph of order n with adjacency matrix A. Let W=[e,Ae,…,A^n-1e] (e is the all-one vector) and Δ=∏_i>j(α_i-α_j)² (α_i's are eigenvalues of A) be the walk matrix and the discriminant of G, respectively. Wang and Yu \citewangyu2016 showed that if θ(G):=gcd\2^{-\lfloor(n)/(2)\rfloor}det W,Δ\ is odd and squarefree, then G is determined by its generalized spectrum (DGS). Using the primary decomposition theorem, we obtain a new criterion for a graph G to be DGS without the squarefreeness assumption on θ(G). Examples are further given to illustrate the effectiveness of the proposed criterion, compared with the two existing methods to deal with the difficulty of non-squarefreeness.

Cited by

• On a generalization of the Johnson-Newman theorem to multiple rank-one perturbations

Related

• Smith Normal Form and the Generalized Spectral Characterization of Graphs
• A simple arithmetic criterion for graphs being determined by their generalized spectra
• An arithmetic criterion for graphs being determined by their generalized A_α-spectrum
• Graphs with at most one generalized cospectral mate
• Generalized Spectral Characterization of Graphs: Revisited