The Nullity Of {C₄, 2K₂}-free Graphs

Nullity is an important positive to characterize singularity of graphs in the spectral graph theory . The nullity of a graph is the multiplicity of the eigenvalue zero in its spectrum . After L.Collatz and U.Sinogowitz first posed the conception of nullity in paper [17] , this problem has been investigated by many researchers . For bipartite graph,trees,unicyclic graphs,bicyclic graphs some particular results are known . In this paper , we mainly discuss the nullity and spectrum of a kind of free graph , that is {C₄,2K₂} - free graphs . Obtain the the range of the nullity on {C₄,2K₂} - free graphs ; Give the nullity set of {C₄,2K₂} -freegraphs ; Characterize the structure of graphs with maximal nullity and minimal nullity .Specially , we characterize the spectrum of {C₄,2K₂} - free graphs attaining the upper bound of nullity and give a range of spectral radius.In Section 2 , we introduction the basic conception,definition and mark of graph theory and nullity . And some main results respect to the nullity of graphs proved by others which we will use in this paper.In Section 3 , Basis on the structure of {C₄,2K₂} - free graphs , we classify this graph as two cases, those are V₃≠φand V₃ =φ。Obtain the the range of the nullity on two cases , and give the nullity set of {C₄,2K₂} - free graphs .Theorem 3.1: Let G be a {C₄,2K₂} - free graphs , if V₃ =φ, |V(G)| = n≥2, then :(1)0≤η(G)≤n-|V₂|(2) Equality holds if V₁ is an isolated vertex set, and spec(G) =(?)Theorem 3.2: Let G be a {C₄,2K₂} - free graphs ,if V₃ =φ, then : the nullity set of G is [0,n-|V₂|].Theorem 3.3: Let G be a {C₄,2K₂} - free graphs ,if V₃≠φ, |V(G)| =n≥2 ,then:0≤η(G)≤n-|V₂|-5.Theorem 3.4: Let G be a {C₄,2K₂} - free graphs ,if V₃≠φ, then : the nullity set of G is [0,n- |V₂| -5] .In Section 4 , By means of a kind of new graphΓ(G) ,it was defined in section 1 . we characterize the structure of graphs with minimal nullity 0 and second smallest nullity 1 under two cases: V₃≠φand V₃=φ. The main results as follows:Theorem 4.1: Let G be a {C₄,2K₂} - free graphs , |V₁|＜|V₂|-1. If G satisfied(1) V₃=φ, for bipartite graph G'=G-E(G[V₂]) ,ε(G')=m(G')=|V₁|(2) V₃≠φ, for bipartite graph G'=G[V₁,V₂]-E(G[V₂]) ,ε(G')=m(G')=|V₁|then :η(G)=0. Theorem 4.3: Let G be a {C₄, 2K₂} - free graphs , G" is the induced subgraph of G' = G[V₁,V₂] - E(G[V₂]) and G" no isolated vertex . If G satisfied :(1)|V₁|<|V₁|-1(2) G is partly decomposable(3) G"≌every subgraph of G^* , each subgraph contains |V₁|K₂Thenη(G) = 0 .Theorem 4.5: Let G be a {C₄,2K₂} - free graphs If G satisfied:(1)|V₁| = |V₂|-1(2) for bipartite graph G' = G[V₁,V₂] - E(G[V₂])≌every subgraph of G^* , each subgraph contains |V₁|K₂(3) G is partly decomposablethen :η(G) = 1 when V₃ =φ;η(G) = 0 when V₃≠φ.In Section 5 , we consider some problems of spectrum . The structure and spectrum of maximal nullity on V₃=φhas been given by theorem 3.1 . But there is much difficult to characterize the structure and spectrum of maximal nullity on V₃≠φ.In order to solve this problem better , we given theorem 5.1 , use theorem 5.1 and other results , at last , characterize the structure and spectrum of maximal nullity on V₃≠φ.Theorem 5.1: Let G' be a simple graph , if G' satisfied :(1) V(G') = V₂∪V₃, V₂ induced a clique , V₃ induced a 5-cycle in G'(2) (?)∈V_i(i=2,3)v₂v₃∈Ethen : (1) (?)=Eig(G'[V₂])∪Eig(G'[V₃])-ρ(G'[V₂])-ρ(G'[V₃]).(2) the largest eigenvalueλ₁ and the smallest eigenvalueλ_n are simple root. They are symmetric about (?).(3) (?) , it's multiple as same as the multiple in graph.(4)λ₁=-(λ₂+…+λ_n).Theorem 5.2: Let G be a {C₄,2K₂}-free graphs , V₃≠φ,|V(G)|=n≥2then : (1) Nullityη(G) is n-|V₂|-5, when V₁ is isolated vertex set.(2) spec(G) =(?).