The Study Of Spectral Determination Of Graphs

The spectral determination theory of graph is a new field in graph theory, which is mainly concerned with the adjacency spectrum, the Laplacian spectrum and the signless Laplacian spectrum. The question "which graphs are determined by their spectra?" goes back for half a century, and originates from chemistry. In 1956, Giinthard and Primas raised the question in a paper that relates the theory of graph spectra to Huckel's theory from chemistry. At that time it was believed that every graph is determined by its spectrum until one year later Collatz and Sinogowitz presented a pair of cospectral graphs. Now, many cospectral graphs have been found out. A graph is said to be determined by its spectrum if there is no other non-isomorphic graph with the same spectrum.The spectral determination theory of graph has been widely studied in recent years. It has great significance not only in graph theory, but also in some fields of computer science, chemistry and physics.The principal method for the research is that:exclude some classes of cospec-tral graphs through a lot of calculation by using Maple and Matlab, and combined with GM(Godsil-Mckay)-switching; conjecture some kinds of graphs which are de-termined by their adjacency spectra or Laplacian spectra; prove that they are de-termined by their adjacency spectra or Laplacian spectra by using known spectral properties of these graphs.Some kinds of non-regular graphs about the adjacency spectra and Laplacian spectra are mainly investigated in the dissertation. The main results are the follow-ing:Some trees are determined by their spectra. Firstly, a counter example is given, which shows that the class of double starlike trees having the same number of vertices on the stars are not determined by their adjacency spectra. Secondly, all the double starlike graphs are proved to be determined by their Laplacian spectra.Some unicyclic graphs are determined by their spectra. Firstly, it is proved that octopus graph, which is obtained from a cycle and a star by identifying the center of the star with a vertex of the cycle, is determined by its Laplacian spectrum. A conjecture is given that octopus graph is determined by its adjacency spectrum. Then, a class of adjacency-cospectral unicyclic graphs and a class of Laplacian-cospectral unicyclic graphs are given by using corresponding matrix switching. At last, a class of unicyclic graphs composed by cycle Cp, path Ps and star K1,q are proved to be determined by their Laplacian spectra.Some bicyclic graphs are determined by their spectra. In a general sense, the proof of the determination of a graph by its adjacency spectrum is more difficult than that of its Laplacian spectrum. Firstly, the smallest bicyclic graph, named sandglass graph, is proved to be determined by its adjacency spectrum as well as its Laplacian spectrum. Then, by using Godsil-Mckay switching, some counter ex-amples of bicyclic graphs are given which are not determined by their adjacency spectra or Laplacian spectra. At last, a bicyclic graph which is obtained by append-ing an odd cycle to each pendant vertex of a path is proved to be determined by its adjacency spectrum.