特征值互不相同的图(英文)

On Graphs with Distinct Eigenvalues

F.Harary和A.J.Schwenk[1]给出了一个开放性问题:什么样的图具有互不相同的特征值?到目前为止关于这方面的研究还很少.在本文中,将完全刻画了直径为d=n 2的连通二部图具有n个互不相同特征值的情况.最后,对直径为d=n 2的连通非二部图的情况给出了部分结果.

In paper [1] EHarary and Schwenk give an open problem： Which graphs have distinct eigenvalues？ Unfortunately, there have been few results on the question. In this paper, we will characterize the connected bipartite graphs that has n distinct eigenvalues with diameter d = n - 2 and give some results about the graphs which are non-bipartite with d = n - 2 in the end.