Some Graphs Are Determined By Their Spectra

The theory of graph spectra is an active and important area in graph theory. There are extensive applications in the fields of quantum chemistry, statistical mechanics, computer science, communication networks and infor-mation science. In the theory of graph spectra, there are various matrices that are naturally associated with a graph, such as the adjacency matrix, the Laplacian matrix, the incidence matrix and so on. Among the above mentioned matrices of graphs, the most important two are the adjacency matrices and the Laplacian matrices of graphs. This thesis mainly researchs the hot problem of Laplacian spectral characterization through investigates Laplacian matrices. In [1], F. Ramezani et al. proved that anyθ-graph is determined by the adjacency spectrum (the multiset of eigenvalues) except possibly when it contains a unique 4-cycle. On the basis of their conclusions, we researchs the Laplacian spectral characterization ofθ-graph, the main conclusions are as follows:1. We have proved thatθ-graphθs1,s2,s3(|si—sj|≤2,1≤i≤j≤3) is determined by its Laplacian spectrum;2. We have proved thatθ-graph of girth 3 is determined by its Lapla-cian spectrum;3. We have proved thatθ-graph of girth 4 is determined by its Lapla-cian spectrum;4. We have proved thatθ-graph ofθ0,u,v(u+v=1(mod 2)) is deter- mined by its Laplacian spectrum;5. On the basis of above conclusions, we give a conjecture on Laplacian spectral characterization ofθ-graph.