Study On Spectral Characteristic Problem For Some Graphs

Let G be a simple graph, and let M = M(G) be a corresponding graph matrix de?ned in a prescribed way. The theory of graph spectra(i.e., M-spectral theory) is a theory in which graphs are studied by means of eigenvalues of a matrix M. The M-polynomial of G is de?ned as det(x I- M), where I is the identity matrix. The M-eigenvalues of G are the eigenvalues of its M-polynomial. The M-spectrum, denoted by SpecM(G), of G is a multiset consisting of the M-eigenvalues. The M-spectral radius of G is the ?rst largest M-eigenvalue of G. Graphs with the same spectrum with respect to a graph matrix M are called M-cospectral graphs. A graph G is said to be determined by its M-spectrum if there is no other non-isomorphic graph with the same spectrum, that is, SpecM(H) = SpecM(G) implies H～= G for any graph H.An M-cospectral mate of G is a graph cospectral with but not isomorphic to G.Moreover, let D be the degree diagonal matrix of G. If M equals its adjacency matrix A, Laplacian matrix L = D- A and Signless Lapalcian matrix Q =D +A, one can obtain some related concepts of adjacency spectrum, Laplacian spectrum and signless Laplacian spectrum, respectively.The spectral characteristics of a graph mainly consider the spectral properties and the spectral characterizations of its graph matrix. From the current researches we see that graph matrices include the vertex-edge incidence matrix, the adjacency matrix, the Laplacian matrix, the signless Laplacian matrix, the distance matrix, the normalized Laplacian matrix, the Seidel matrix and generalized adjacency matrix and so on. For the spectral properties,spectral radius and its related topics are always an important part of studying on the graph spectral problem. Meanwhile, the 2-th, 3-th largest eigenvalue,and the smallest, the second smallest eigenvalue of some graph matrix are also some hot research subjects in recent years. Spectral characterizations primarily describe some graphs with such spectral characteristics by the given spectral characteristics, in which the graph determined by its spectrum is a very thorny task on spectral characterizations, and it is also a core domain on studying of graph spectra. As far as all DM S-graphs are concerned, the study focus on three classes graphs, the ?rst class is the graph with relatively simple and symmetric structure; the second class is the irregular graph that at most has four distinct degree; the third class is the graph whose shape can be determined only by its degree sequence. However, for a given graph in one of the above three classes, determining it to be DM S-graph is also a very di?cult problem.In this work, we focus on investigating some DM S-graphs by graph structure, combinatorics, matrix theory, the close walk formula, characteristic polynomial, eigenvector, eigenvalues and the bound of eigenvalue, spectral moments and the degree sequence. Meanwhile, we consider the spectral properties of some other graphs. On the graph determined by its spectrum, we prove our results around two questions such as “Whether a graph is determined by its spectrum? if not, can we determine its cospectral graphs?” In the thesis,the second chapter, the third chapter and the fourth chapter mainly study the DM S-problem of adjacency spectrum, Laplacian spectrum and signless Laplacian spectrum for some graphs, respectively. The ?fth chapter mainly construct some in?nity cospectral mates of graphs by graph operations.In this paper, a brief organization is given in the following.In Chapter 1, we ?rstly introduce the background and some applications of graph spectra, then we give the notions, symbols and graphs involved in this work. Thirdly we brie?y summarize the source, background of the DMSproblem. At last, we list our main results of the thesis.In Chapter 2, we ?rst obtain sharp lower and upper bounds for the spectral radius of a graph so called barbell by considering the principal vector. Moreover, we present the characteristic polynomial and spectral radius equations of the graph; then we prove that all line graphs of T-shape tree are determined by their A-spectra with some exceptions. Furthermore, we give the A-cospectral graphs of those exceptions.In Chapter 3, we ?rstly give the relation between Laplacian spectrum and packing number of a graph. Secondly, we consider the Laplacian spectral characterization of some graphs in the following: at ?rst, we prove that no two non-isomorphic line graphs of T-shape tree are L-cospectral; then we give a complete spectral characterization for one type of Π-shape tree. It is interesting that we ?nd an in?nitely many pairs of L-cospectral tree in the type; next, we show that all wind-wheel graphs are determined by their Lspectra. At last, we mainly study some degree sequences determined by the Laplacian spectrum of the corresponding graph.In Chapter 4, we ?rst consider some basic properties of Q-spectrum of a graph, which can be viewed a translation from A-spectrum to Q-spectrum;then we prove that all wind-wheel graphs are determined by their Q-spectra,from the result we obtain that the friendship graph is also determined by its Q-spectrum.In Chapter 5, we introduce two new graph operations such as subdivision vertex-edge neighbourhood vertex-corona and subdivision vertex-edge neighbourhood edge-corona on Gi(i = 1, 2, 3), and the result graphs are denoted by GS1??(GV2∪ GE3) and GS1(GV2∪ GE3), respectively. Subsequently, the adjacency spectrum, the Laplacian spectrum and the signless Laplacian spectrum of GS1??(GV2∪ GE3)(respectively, GS1(GV2∪ GE3)) are determined in terms of G1, G2 and G3. As applications, we construct in?nitely many pairs of cospectral graphs. Meanwhile, we give the give the number of spanning trees of GS1??(GV2∪ GE3) and GS1(GV2∪ GE3), respectively.