Spectral Integral Variation Of Graph And Laplacian Integral Graph

Spectral graph theory mainly studies the relations between the spectral property and the structural property. The spectral perturbation and Laplacian integral graph arc very important topics in spectral graph theory, which arc used to reflect the structural property of graphs.This thesis mainly discuss two problems: (1) the spectral integral variation of graphs, that is, the Laplacian spectrum changes with integral perturbations after adding an edge, (2) Laplacian integral graph, that is, the graph with all Laplacian eigenvalues being integers.The organization of this thesis is as follows. In Chapter 1, we introduce a background of the spectral graph theory, spectral perturbation and Laplacian integral graph. In Chapter 2, we discuss the spectral integral variation of trees. In Chapter 3, we discuss the Laplacian integral graph with exactly three distinct cigcnvalucs.In 2002 Fan introduced the notion of spectral integral variation to construct Laplacian integral graphs. Kirkland (2004) and Pati et.al. (2005) studied the spectral integral variation of graphs, and obtained some valuable results. In Chapter 2, we investigate the the spectral integral variation of trees, and give a complete characterization. We also discuss the spectral integral variation of trees with one changed cigcnvaluc being algebraic connectivity, and also solve this problem.Merris proved that degree maximal graphs are Laplacian integral in 1994. In 2005 Fallat and Kirkland et. al. discuss an extreme case of Laplacian integral graphs, i.e. Laplacian integral graphs with all eigenvalues distinct. In Chapter three, we consider another extreme case of Laplacian integral graphs, i.e. Laplacian integral graphs with exactly three distince cigenvalues, and give characterizations of some cases of this problem.