Characterization Of Q-Integral Unicyclic,Bicyclic And Tricyclic Graphs

Spectral graph theory is an important research field in algebraic graph theory. Spectral graph theory mainly investigate the relations between the structural properties and adjacency spectra, Laplacian spectra or signless Laplacian spectra of graphs. Spectral graph theory has important applications in chemistry, theoretical physics, quantum mechanics and computer science. The characterization of integral graphs raised from an open problem posed by Harary and Schwenk [21] in 1974: “Which graphs have entirely integral eigenvalues?” Recently, it is found that integral graphs can play a key role in the so called perfect state transfer in quantum spin networks [6].All the signless Laplacian eigenvalues(in short, Q–eigenvalues) of a graph together with their multiplicities are called the signless Laplacian spectrum(in short, Q–spectrum)of the graph. A graph is called signless Laplacian integral(in short, Q–integral) if its Q–spectrum consists of integers. A connected graph with n vertices and m edges is called a k–cyclic graph if k = m- n + 1. In this paper, we determine all the Q–integral unicyclic,bicyclic and tricyclic graphs.This paper is organized as follows. In Chapter 1, we first introduce some research background and applications of spectral graph theory and the problem of characterizing integral graphs. Next we introduce some useful definitions and symbols. At last we list some known results about integral graphs. Chapter 2 contains two sections. In the first section, we list some useful lemmas about Q–eigenvalues and Q–integral graphs. In the second section, we characterize a class of k–cyclic graphs whose second least Q–eigenvalue is less than one. In Chapter 3, we mainly use the results we have obtained to characterize Q–integral graphs. Chapter 3 contains two sections. In the first section, we determine all the Q–integral unicyclic and bicyclic graphs. In the second section, we determine all the Q–integral tricyclic graphs.