Sábháilte in:
| Príomhchruthaitheoirí: | , |
|---|---|
| Formáid: | Preprint |
| Foilsithe / Cruthaithe: |
2021
|
| Ábhair: | |
| Rochtain ar líne: | https://arxiv.org/abs/2110.09404 |
| Clibeanna: |
Cuir clib leis
Níl clibeanna ann, Bí ar an gcéad duine le clib a chur leis an taifead seo!
|
| _version_ | 1866917793326170112 |
|---|---|
| author | Wang, Wei Wang, Wei Zhu, Fuhai |
| author_facet | Wang, Wei Wang, Wei Zhu, Fuhai |
| contents | A fundamental and challenging problem in spectral graph theory is to characterize which graphs are uniquely determined by their spectra. In Wang [J. Combin. Theory, Ser. B, 122 (2017): 438-451], the author proved that an $n$-vertex graph $G$ is uniquely determined by its generalized spectrum (DGS) whenever $2^{-\lfloor\frac{n}{2}\rfloor}\det W$ is odd and square-free. Here, $W$ is the walk matrix of $G$, namely, $W=[e,Ae,\ldots,A^{n-1}e]$ with $e$ 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 polynomials for a graph $G$ associated with a prime $p$. Such a polynomial is invariant under generalized cospectrality. Using the newly defined polynomials, 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2110_09404 |
| institution | arXiv |
| publishDate | 2021 |
| record_format | arxiv |
| spellingShingle | An improved condition for a graph to be determined by its generalized spectrum Wang, Wei Wang, Wei Zhu, Fuhai Combinatorics 05C50 A fundamental and challenging problem in spectral graph theory is to characterize which graphs are uniquely determined by their spectra. In Wang [J. Combin. Theory, Ser. B, 122 (2017): 438-451], the author proved that an $n$-vertex graph $G$ is uniquely determined by its generalized spectrum (DGS) whenever $2^{-\lfloor\frac{n}{2}\rfloor}\det W$ is odd and square-free. Here, $W$ is the walk matrix of $G$, namely, $W=[e,Ae,\ldots,A^{n-1}e]$ with $e$ 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 polynomials for a graph $G$ associated with a prime $p$. Such a polynomial is invariant under generalized cospectrality. Using the newly defined polynomials, 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. |
| title | An improved condition for a graph to be determined by its generalized spectrum |
| topic | Combinatorics 05C50 |
| url | https://arxiv.org/abs/2110.09404 |