A simple arithmetic criterion for graphs being determined by their generalized spectra

详细信息    查看全文

• 作者：Wei Wang ^{wang_weiw@163.com}
• 关键词：Spectra of graphs ; Cospectral graphs ; Determined by spectrum
• 刊名：Journal of Combinatorial Theory, Series B
• 出版年：2017
• 出版时间：January 2017
• 年：2017
• 卷：122
• 期：Complete
• 页码：438-451
• 全文大小：377 K
• 卷排序：122

文摘

A graph G is said to be determined by its generalized spectrum (DGS for short) if, whenever H is a graph such that H and G are cospectral with cospectral complements, then H must be isomorphic to G.It turns out that whether a graph G is DGS is closely related to the arithmetic properties of its walk-matrix. More precisely, let A be the adjacency matrix of a graph G on n   vertices, and let W=[e,Ae,A2e,⋯,An−1e]W=[e,Ae,A2e,⋯,An−1e] (e is the all-ones vector) be its walk-matrix. In Wang (2013) [16], the author defined a large family of graphsFn={G|det(W)2⌊n2⌋is an odd square-free integer} (which may have positive density among all graphs, as suggested by some numerical experiments) and conjectured every graph in FnFn is DGS.In this paper, we show that the conjecture is actually true, thereby giving a simple arithmetic condition for determining whether a graph is DGS.