The Nullity Of Unicyclic Graphs

A unicyclic graph is a simple connected graph with equal number of verticesand edges. Let A be a (0,1)-adjacency matrix of G. The set of all eigenvalues ofA including multiplicity is called the spectrum of G, which is denoted by spec(G).The number of zero eigenvalues in spec(G) is called its nullity which is denotedbyη(G). A graph G is said to be singular (nonsingular) if its adjacency matrixA is a singular (nonsingular) matrix.In [1] L.Collatz and U.Sinogowitz posed the problem of characterizing allgraphs which have the number zero in their spectrum. The nullity of a graph is ofgreat interest in chemistry, because, as has been shown in [2], for a bipartite graphG (corresponding to an alternate hydrocarbon), ifη(G) > 0, then it indicatesthat the molecule which such a graph represents is unstable. Some related resultson trees and bipartite graphs can be found in [3-7]. Recently, Tan Xuezhong andLiu Bolian in [8] obtained the nullity set of n-vertex unicyclic graphs, and gavea su?cient condition for the unicyclic graphs with nullity 0 and asked a problemthat if this condition is also necessary. The main results of this paper can bedivided into three parts. The first part give the confirm answer for this problem,the second part give a formula to calculate the nullity of unicyclic graphs, thethird part discuss nullity of the line graph of any connected graph G.In chapter one, introduce the background, terminology and some importantresults.In chapter two, First we introduce a notion of elementary unicyclic graph,Next we give the su?cient and necessary conditions for the unicyclic graphs withnullity 0.In chapter three, we introduce a new notion of PED-graph and give a formulato calculate its nullity. Then by means of maximum matching number we give aformula to calculate the nullity of unicyclic graphs.In chapter four, we study the nullity of the line graph of any connected graphG. For line graphs, we obtain the following results.1. If G is a connected graph with n vertices and e edges, thenη(L(G))≤e ? n + 2.2. A unicyclic graph U is a simple connected graph with equal number ofvertices and edges. by theorem, we haveη(L(U)) = 0,1,or 2Let G1 and G2 be two graphs with v1∈G1 and v2∈G2. Let G be a graphobtained from G1 and G2 by connecting them by an edge e = v1v2 which isdenoted by G = G1 + G2 and called the join of G1 and G2.3. Let T be a tree withη(L(T)) = 1, then the line graph of the unicyclicgraph G = Cl + T (l≡0 (mod4)) has nullity 2.