On The Further Discussions Of The Nullity And Singularity Of Graphs

The theory of graph spectra is a relatively new field in graph theory, and is also one of the main branches in algebraic graph theory. It originated from the techniques, which was first used by theoretic chemists and physicists, of seeking approximate numerical solution for certain partial differential equations. The fun-damental paper (1957) of L.Collatz and U.Sinogowitz is usually considered as the starting point of the study of graph spectra theory. Two kinds of graph spectra-the spectra of adjacency matrices and that spectra of Laplacian matrices, has been widely studied in the past several decades. The principal method for the research is by using the matrix representation of a graph, combined with matrix theory and the classical results in graph theory, to impulse the theoretical research of graph theory. These research results have great significance not only in graph theory, but also in some fields of chemistry and physics (refer to [3]).In this thesis, we mainly characterize bipartite graphs which meet certain con-ditions and investigate the singularity of the complement of a tree on n vertices with diameter n-1,n-2 or n-3. This thesis consists of three chapters.In chapter 1, we shall introduce the basic concepts, and we shall also state the related research background and list-some representative results in this field.In chapter 2. the problem related with extremal graph theory, i.e., given a set of graphs, find an upper bound for the nullity of graphs in this set and characterize the graphs in which the maximal nullity is attained, is studied further on the basis of others. We are very interested in the bipartite graphs with n vertices and given diameter. So a complete characterizations on these extremal graphs are obtained.In chapter 3, the singularity of the complement graphs of trees is studied by using the methods of spectral graph theory. The general judgement methods for the singularity of the complement of trees with diameter n-1, n-2 or n-3 are established. These results extend the related results on tree with diameter less than 5 and non-singular complement.