Study On Two Classes Of Graphs Determined By Their Spectra

The theory of graph spectra originated from a discrete graph model, which was ?rst used by theoretic chemists and physicists to seek numerical solution of certain partial di?erential equations. It has a wide range of applications in physics, chemistry, computer science, communication networks, etc. The theory of graph spectra mainly studies combinatorial property of a graph through spectral characterization(the multiset of eigenvalues) of some matrices associated with the graph(e.g. adjacency matrix A, Laplacian matrix L = D- A, signless Laplacian matrix Q = D + A, normalized Laplacian matrix?L = D-12 LD-12, Seidel matrix S = J- 2A- I, etc). It is an important research ?eld of algebraic graph theory. The research content of graph spectra theory is quite broad, and mainly includes two aspects. One is the spectral characterization of graphs, it involves estimating the eigenvalues, determining the distribution of the spectra, studying the relation between the spectra and the invariants(e.g. diameter, chromatic number, girth, connectivity, etc) of graphs; the other one is the problem of characterizing graphs through their spectra, where which graphs are determined by their spectra(DS problem for short) is a problem famous and di?cult.Two graphs are called cospectral if they share the same spectrum. Cospectral graphs are not necessarily isomorphic, but two isomorphic graphs must be cospectral. A graph G is called DS if, for any H cospectral with G, we have H is isomorphic to G. The question “which graphs are DS?” includes two sections, one is whether a graph is determined by its spectrum; the other one is if not, can we determine all its cospectral graphs. G¨unthard and Primas?rst raised the question“which graphs are DS?” then van Dam and Haemers had published two survey which include many cospectral mates and give some necessary conditions about cospectral graphs. But the question is far from resolved. From the known results, graphs with certain special property are considered, such as graphs with symmetric property, graphs with small spectral radius, graphs with a small number of distinct eigenvalues, non-regular graphs with few distinct degrees(e.g. almost regular graphs) and so on. Although we have obtained many results about DS-graph, the answer to the question is still di?cult. This thesis is focus on the DS problem of two classes of graphs. One is the spectral characterization of unicyclic graphs whose second largest eigenvalue does not exceed 1; the other one is Laplacian and signless Laplacian spectral characterization of 4-rose graphs. This thesis is organized as follows:In Chapter 1, ?rstly, we simply introduce the research background and some applications of the theory of graph spectra. Secondly, we give the notions, symbols. Thirdly, we summarize the source, background, overseas and domestic research status of the DS problem. In addition, we generalize some frequently used tools and techniques of the DS problem. At last we outline the main results of this thesis.Many research results have been obtained about the problem of characterizing graphs with second largest eigenvalue not great than 1. In Chapter 2, we consider the DS problem of unicyclic graphs with second largest eigenvalue not exceeding 1. Firstly, we classify these graphs and prove that these graphs are not A-cospectral. Secondly, we obtain some necessary condition for a graph being A-cospectral with the unicyclic graph whose second largest eigenvalue does not exceed 1. Then we consider the spectral characterization of these graphs according to the classi?cation. We put emphasis up on investigating the spectral characterization of the graph Gt,s. Based on some forbidden subgraphs, ?nally we prove that, except for four graphs, all the other unicyclic graphs whose second largest eigenvalue does not exceed 1 are determined by their adjacency spectra.The spectral characterization of p-rose graph(is a graph consisting of p cycles sharing a common vertex) deserves further attention. In Chapter 3, we consider the Laplacian spectral characterization of 4-rose graphs. First of all we introduce a necessary condition about L-cospectral graph. Then we get the antepenultimate coe?cient of the Laplacian characteristic polynomial of the 4-rose graph through its combinatorial structure. In addition, we compute the Laplacian characteristic polynomial of 4-rose graph. In the end, by determining the degree sequence of graph L-cospectral with 4-rose graph we show that 4-rose graphs are determined by their Laplacian spectra.In Chapter 4, we investigate the signless Laplacian spectral characterization of 4-rose graphs. First of all we introduce a new invariant for Q-cospectral graph and present the signless Laplacian characteristic polynomial of the 4-rose graph. Then we give rough structures of graphs which are Q-cospectral with4-rose graph. Next, according to the new invariant for Q-cospectral graph and the number of triangles of graph, we determine the degree sequence of graphs which are Q-cospectral with 4-rose graph. In the end, it will be shown that4-rose graphs are determined by their signless Laplacian spectra.