The Nullity Of Graphs

The nullity of a graph is defined to be the multiplicity of the zero eigen-value in the adjacency spectrum of the graph, which origins from quantum chemistry. A graph is called singular if its nullity is zero. In the fifties of last century, Longuet-Higgins found:If G is biparite and its nullity is positive, the alternant hydrocarbon corresponding to G is unstable. In 1957, Collatz et.al. first posed the problem of characterizing nonsingular or singular graphs for discussing the stability of the molecular structure. In past thirty years, this problem has received a lot of attention in chemistry and mathematics. The main work was focused on the follows problems:characterizing the singularity of special graphs, characterizing the nullity set of graphs, characterizing the structure of graphs with fixed nullity, characterizing graphs with large nullity. The latter is a hot topic in spectral graph theory.This thesis mainly discusses the structures of some classes of graphs with large nullity. By the nullity decomposition theory of graphs with pendant trees, we characterize the structures of unicyclic graphs with nullity n-5, n-6,n-7, respectively, and the structures of bicyclic graphs with nullity n-4, n-5, n-6, respectively.The organization of this thesis is as follows. In Chapter 1, we introduce a brief background of the adjacency spectral theory and the nullity of graphs, give some notations which we will be used in the following sections, introduce the problems and its development, and list the main results we obtained in this thesis. In Chapter 2, we characterize the structures of unicyclic graphs with nullity n-5, n-6, n-7 respectively by a new approach. In the last chapter, a general approach to the nullity of bicyclic is given. By using this approach, we characterize the structures of bicyclic graphs with nullity n-4, n-5, n-6, respectively.