On Graphs With Distinct Eigenvalues

The eigenvalues of graphs is a crossing area between graph theory and algebra. It isalso a branch of algebraic graph theory. In paper [1] F. Harary and A. J. Schwenk givean open problem: Which graphs have distinct eigenvalues? Unfortunately, there havebeen few results on the question. In this paper, we will characterize the connected graphsthat has n distinct eigenvalues with diameter d = n -2, using characteristic polynomialand interlace theorem. The main results are as follows:In the first chapter, introduction, we give the basic definitions, symbols and nota-tions about eigenvalue, and recalled the history and status quo of the eigenvalue. Wealso list list some important known results about the k distinct eigenvalues.The second chapter consists of three sections. In the first section, we introduce somesome important lemmas, corollaries. Let G be a graph with n vertices and diameterd(G) = n - 2. In this section, we will give the simple structure of G (see Fig.2). Byconsidering whether the graphs are bipartite or not, we can distinguish the four typesgraphs into two classes: D_n-2⁰ = {P_n-1^k+1,P_n-1^k,k+2| 1≤k≤n - 3}, and the last two typesin D_n-2¹ = {P_n-1^k,k+1(1≤k≤n - 2),P_n-1^k,k+1,k+2 (1≤k≤n - 3}. In the third section, wewill completely characterize the graphs in D_n-2⁰ with distinct eigenvalues.In the third chapter, We first introduced interlace theorem. At last use interlacetheorem and eigenvectors of the graphs obtain: Let G be a graph shown in Fig.4(a), (b),where n≥4. If 3(?)n, then G has n distinct eigenvalues.