Spectral Characterizations Of Graphs And Related Topics

A spectral graph theory is a theory in which graphs are studied by means of eigenvalues of a matrix M which is in a prescribed way defined for any graph. This theory is called M-theory. Graphs matrices include the incidence matrix, the adjacency matrix A, the Laplacian matrix L, the normalized Lapla-cian matrix and Seidel matrix and so on. Recently, the famous specialists in spectral graph theory Cvetkovic, Rowlinson and Simic[42] posed and discussed the possibilities for developing a spectral theory of graphs based on signless Lapalcian matrix Q. Simultaneitily, they pointed that studying graphs by Q-spectra is more efficient than studying them by their adjacency spectra. van Dam and Haemers [52] also mentioned that the signless Laplacian seems to be the most convenient for use in studying graph properties. The contents of this thesis contain the A-theory, Q-theory and L-theory, especially for the first two theories.The M-eigenvalues of a graphs are those of its graph matrix M. The M-spectrum, denoted by SpecM(G), of G is a multiset consisting of its M-eigenvalues. Two graphs G and H are called M-cospectral graphs if SpecM(G) = SpecM(H) and denoted by G-M H. The M-cospectral class of G is defined as[G]M={H| H-M G}. A graph G is said to be determined by its M-spectrum (or G is a DMS-graph for short) if SpecM(H)= SpecM(G) implies H(?) G for any graph H. The thesis mainly investigates the spectral charac-terizations of graphs and the related topics. The M-Spectral Characterization Problem (M-SCP) of a graph G is posed as follows:M-SCP1:Is G a DMS-graph?M-SCP2:If G is not a DMS-graph, can we determine [G]M?When we study the M-SCP, it is helpful for us to know much more neces-sary conditions. Thus, we also research the problems relating to the spectral characterizations of graphs. Moveover, the results obtained are powerful tools to solve the M-SCP. The main results of the thesis are the following:In Chapter 2, we mainly investigate the A-SCP and the related topics. Firstly, we determine the A-cospectral classes of three families of graphs hav-ing an isolated vertex; Secondly, we study the A-index of DK-graphs and unicyclic graphs, determine the A-cospectral class of a kind of DK-graphs, give a necessary and sufficient condition for author kind of DK-graphs, and study the divisibility among A-polynomials of graphs; Thirdly, the A-SCP1 of two kinds of connected (2,3)-almost regular graphs, i.e., dumbbell graphs andθ-graphs, are researched.In Chapter 3, we mainly investigate the Q-SCP and the related topics. Firstly, the relations among the spectral characterizations of graphs are de-fined; Secondly, we determine all the limit points less than 4.38+ of Q-index, characterize respectively the connected graphs whose Q-index lies in (4,2+(?)], (2+(?), (?)+2] and ((?)+2,4.5] with (?)≈2.38+, give an upper bound for the Q-index and obtain the graphs achieving the bound; Thirdly, we give an upper bound for the second largest Q-eigenvalueκ2, characterize all the connected graphs withκ2∈[0,3] and completely solve the Q-SCP of these graphs; Fourthly, by means of the coefficients of Q-polynomial of a graph G we define two Q-cospectral invariants named the first character I1(G) and the the second character I2(G), prove I1(G)≤1 and determine respectively the connected graphs with I1(G)=1,0,-1,-2,-3, show I2(G)≥-2 and determine the graphs achieving the equality, use the first character to study the Q-SCP1 of a graph; Fifthly, we find a method how to determine the degree sequence of a graph Q-cospectral to a given graph, and employ this method to obtain the degree sequence of graphs Q-cospectral to 2-rose graphs and 3-rose graphs respectively, and further completely solve the Q-SCP of 2-rose graphs and 3-rose graphs; Sixthly, we determine the maximal graph with fixed order and diameter, and the maximal one with fixed order and number of cut points.In Chapter 4, we mainly investigate the L-SCP and the related topics. Firstly, we extend the Q-characters to the L-characters, use L-character to study the L-SCP; Secondly, the L-SCPs of 2-rose graphs and 3-rose graphs are partially solved; In the end, the connected graphs whose L-index belongs to [0,4],(4,2+(?)] and (2+(?),2+(?)] are respectively determined. Moreover, the L-SCP of disjoint union of paths and cycles are fully solved.