On The Characterization Of Laplacian Integral Graphs

Spectral graph theory is an active research ?eld in graph theory. Spectral graph theory mainly studies the graph properties relate to the characteristic polynomial, eigenvalues and eigenvectors of adjacency matrix, Laplacian matrix or signless Laplacian matrix, and the relation between these properties and the structure properties of graphs. Spectral graph theory has wide applications in computer science, chemistry and physics. In 1973 Harary and Schwenk [1] posed a famous question: “Which graphs have integral spectra?”It has been discovered recently [2] that integral graphs can play a role in the so called perfect state transfer in quantum spin networks.A graph is called Laplacian integral if all its Laplacian eigenvalues are integers. A connected graph with n vertices and m edges is called a k–cyclic graph if k = m- n + 1.Denote by Gk-1the set of(k- 1)–cyclic graphs each of them contains some generalized θ–graph θ(n1, n2,..., nk) as its induced subgraph. In this paper, we completely characterize the Laplacian integral tricyclic graphs, and determine all the Laplacian integral graphs in Gk-1. By the way, we show that all the Laplacian integral tricyclic graphs are determined by their Laplacian spectra.This paper is organized as follows. In Chapter 1, we ?rst introduce some background of spectral graph theory, the raise of the problem about integral graphs and some relevant applications. Next we introduce some fundamental notions and symbols. At last we list some known results about integral graphs. Chapter 2 contains three sections. In the?rst section, we list some useful lemmas for latter use. In the second section, we give an edge subdividing theorem for Laplacian eigenvalues of a graph. In the third section,we characterize a class of k–cyclic graphs whose algebraic connectivity is less than one.In Chapter 3, we mainly use the results we have obtained in the previous chapter to characterize Laplacian integral graphs. This chapter contains two sections. In the ?rst section, we completely characterize the Laplacian integral tricyclic graphs, and show that all the Laplacian integral tricyclic graphs are determined by their Laplacian spectra. In the second section, we determine all the Laplacian integral graphs in a class of(k- 1)–cyclic graphs—Gk-1.