Primary decomposition theorem and generalized spectral characterization of graphs
This paper investigates the problem of determining the graphs with respect to their generalized spectrum (DGS), with a focus on controllable graphs. A graph \(G\) is said to be controllable if the determinant of its walk matrix is nonzero. It is known, by a conjecture of \textit{C. Godsil} [Ann. Comb. 16, No. 4, 733--744 (2012; Zbl 1256.05139)] later confirmed by \textit{S. O'Rourke} and \textit{B. Touri} [SIAM J. Control Optim. 54, No. 6, 3347--3378 (2016; Zbl 1352.93027)], that almost all graphs are controllable.\N\NThe key tools used in the paper are: the walk matrix of a graph \(W = [e, Ae, \ldots, A^{n-1}e]\), where \(A\) is the adjacency matrix and \(e\) is the all-ones vector; the discriminant of a graph \(\Delta=\prod_{i>j}(\alpha_i-\alpha_j)^2\) where the \(\alpha_i\)'s are the eigenvalues of \(A\). The main invariant used is: \(\theta(G) := \text{gcd}\{2^{-\lfloor \frac{n}{2}\rfloor}\det W, \Delta\}\). Previous work [\textit{W. Wang} and \textit{T. Yu}, ``Square-free discriminants of matrices and the generalized spectral characterizations of graphs, Preprint, \url{arXiv:1608.01144}] showed that if \(\theta(G)\) is odd and squarefree, then \(G\) is DGS. \N\NThe main contribution of this paper is to remove the squarefreeness assumption. Using the primary decomposition theorem and the Smith normal form, the authors establish a new criterion: For a controllable graph \(G\), if \(\theta(G)\) is odd, then under certain conditions on the multiplicities of irreducible factors of \(\Phi_p(G;x)\) (a polynomial defined via greatest common divisors of characteristic polynomials), the graph is DGS. This condition carefully compares \(p\)-adic valuations of determinants associated with \(A\) and \(A+J\), where \(J\) is the all-ones matrix.\N\NAn immediate corollary states: if \(\theta(G)\) is odd and each \(\Phi_p(G;x)\) is squarefree over \(\mathbb{F}_p\), then \(G\) is DGS.\N\NSeveral examples are presented to demonstrate the effectiveness of the new criterion. Notably, the method succeeds in cases where earlier approaches fail, highlighting the usefulness of the new criterion.
- \(p\)-adic numbers. An introduction
- A new criterion for oriented graphs to be determined by their generalized skew spectrum
- A note on cospectral graphs
- A simple arithmetic criterion for graphs being determined by their generalized spectra
- A sufficient condition for a family of graphs being determined by their generalized spectra
- An improved condition for a graph to be determined by its generalized spectrum
- Controllable subsets in graphs
- Generalized spectral characterization of graphs revisited
- Generalized spectral characterization of signed trees
- Generalized spectral characterizations of a new family of noncontrollable graphs
- Generalized spectral characterizations of almost controllable graphs
- Haemers’ Conjecture: An Algorithmic Perspective
- scientific article; zbMATH DE number 3336895 (Why is no real title available?)
- Mixed graphs determined by their generalized Hermitian adjacency spectrum based on Eisenstein integers
- Modern computer algebra
- On a Conjecture of Godsil Concerning Controllable Random Graphs
- On the generalized A_-spectral characterizations of almost -controllable graphs
- Proof of a conjecture on the determinant of the walk matrix of rooted product with a path
- Smith normal form and the generalized spectral characterization of graphs
This page was built for publication: Primary decomposition theorem and generalized spectral characterization of graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6939599)
