An improved condition for a graph to be determined by its generalized spectrum
An improved condition for a graph to be determined by its generalized spectrum
复制标题
DOI：
10.1016/j.ejc.2022.103638
复制
发表时间：
2021-10
期刊：
影响因子：
--
通讯作者：
W. Wang;Fuhai Zhu
中科院分区：
文献类型：
--
作者：
W. Wang;Fuhai Zhu
A fundamental and challenging problem in spectral graph theory is to characterize which graphs are uniquely determined by their spectra. In Wang (2017), the author proved that an n-vertex graph G is uniquely determined by its generalized spectrum (DGS) whenever 2−⌊ n 2⌋ det W is odd and square-free. Here, W is the walk matrix of G, namely, W=[e, A e,…, A n− 1 e] with e the all-one vector and A the adjacency matrix of G. In this paper, we focus on a larger family of graphs with d n square-free, where d n refers to the last invariant factor of W. We introduce a new kind of polynomial for a graph G associated with a prime p. Such a polynomial is invariant under generalized cospectrality. Using the newly defined polynomial, we obtain a sufficient condition for a graph in the larger family to be DGS. The main result of this paper improves upon the aforementioned result of Wang while the proof for the main result gives a new way to attack the problem of generalized spectral characterization of graphs.
