The Nullity Of Signed 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 nonsingular if its nullity is positive. 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, has been a hot topic in spectral graph theory.A signed graph is a graph with a sign(+or-) attached to each of its edges. Signed graphs were introduced by Harary in connection with the study of the theory of social balance in social psychology. Subsequently, a number of problems of graphs were extended to those of signed graphs. In this thesis, we introduce the nullity of signed graphs, and give some results on the nullity of signed graphs with pendant trees. Using these results, we characterize the unicyclic signed graphs of order n with nullity n-2, n-3, n-4, n-5, n-6, n-7, respectively, the bicyclic signed graphs of order n with nullity n-2, n-3, respectively, and the bicyclic signed graphs of order n and nullity n-4 which contains pendant trees.This thesis is organized as follows. In Chapter one, 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 two, we give the nullity decomposition theorem of signed graphs with pendant trees and characterize the unicyclic signed graphs of order n with nullity n-2,n-3,n-4,n-5,n-6,n-7, respectively. In final Chapter, the classification of bicyclic graphs with pendant trees is given. Using this classification and nullity decomposition theorem, we characterize the bicyclic signed graphs of order n with nullity n-2,n-3, respectively, and characterize the bicyclic signed graphs of order n and nullity n-4 which contains pendant trees.