Figure Dn And Qn

Spectral graph theory is concerned with the use of algebraic techniques in the study of the spectrums of graphs. Which graphs are determined by their spectrums is a famous question in the theory, but it is very difficult to answer. As far as we know, it is far from resolved. Usually, a graph G is called spectrally determined if any graph with the same spectrum is isomorphic to G , we call it DS (determined by the spectrum). More generally, it is impossible to characterize a graph by its spectrum, which is obtained from the specific matrix such as the adjacency matrix, the Laplacian matrix, or their normalized forms, except for some graphs with special structures.As the problem is so hard to solve, we concentrate on the graphs with simple structures such as graphs D_n and Q_n , a graph D_n is the graph obtained from C₃∪P_n by adding an edge to connect a vertex of C₃ and a vertex of degree 1 in P_n , where C₃ denotes the cycle with 3 vertices, and P_n denotes the path with n vertices; a graph Q_n is the graph obtained from C_n∪P₁ by adding an edge to connect a vertex of C_n and P₁ , where C_n denotes the cycle with n vertices, and P₁ denotes an isolated vertex. In this thesis, we will prove that graphs D_n and Q_n are determined by their adjacency spectrums. Furthermore, we define two graphs E_n and Q_n,2,which are similar to graphs D_n and Q_n respectively. By estimating the spectral radius of the two graphs, we can prove that graphs E_n and Q_n,2 are also determined by their adjacency spectrums.