The Nullity Of A Graph In Terms Of Independence Number And The Number Of Pendant Vertices

Algebraic graph theory is an active and important field in graph theory, the nullity of G is also an important field in the algebraic graph theory.Let G be a connected simple graph of order n. By ?(G), ?(G),?(G), p(G) we respectively denote the nullity, the independence number, the dimension of cycle space, and the number of pendent vertices of G. In this thesis, we mainly discuss the nullity of a graph in terms of independence number and the number of pendant vertices. The main contents of the thesis are as follows. In Section 1, we mainly introduce the development of algebraic graph theory, the background of research and the basic definitions of graph theory. In Section 2, we introduce some fundamental lemmas. In Section 3, we give an equation describing the connection between the nullity and the independence number of a tree. In Section 4, we extend the result of Section 3 from a tree to an arbitrary connected simple graph, and obtain an upper bound and a lower bound for the nullity of a graph in terms of its independence number, proving that 2?-n???2?-n+2c, Where c refers to the number of cycles contained in G. In particular, it is proved that ?= 2?- n for a tree. In Section 5, we focus attention on unicyclic graphs, using independence number to characterize the nullity of a unicyclic graph. The nullity of a unicyclic graph is characterized explicitly. In Section 6, we prove the inequality of Theorem1.1 ?(G)?2?(G)+p(G). In addition, we characterize the extremal graphs with ?(G)=2?(G)+p(G).