The Spectrum Of Linear Hypergraph

Hypergraph is generalization of general graph. In a simple graph G = (V,E), let A(G) bethe adjacency matrix of G. The eigenvalue of A(G) is called the eigenvalue of G, and thespectrum of A(G) is the spectrum of G. The maximum of the moduli of its eigenvalue iscalled the spectral radius of G. In 1996, KeqinFeng gave the definition of the adjacencymatrix of hypergraph, i.e. the adjacency matrix A = A(H) whose rows and columns are pa-rameterized by the vertices of H, and the vivj entry of A is the number of paths in associatedbigraph B from vi to vj of length 2 and no backtracking.In other words, the aij entry of Ais equal to k if the vertices vi and vj belong to k edges. Similarly, the eigenvalues of A iscalled the eigenvalue of H.and the spectrum of A is the spectrum of H. The maximum ofthe moduli of its eigenvalue is called the spectral radius of H. On the basis of the definitionof the adjacency matrix of H, we investigate the spectral radius of the r-uniform linear hy-pergraph.In the first part we introduce the domestic and foreign research background of this papet.In the second part we introduce the general concepts.In the third part we generate the classic results in graph theory, first of all,we generatePerron-Frobenius theorem and interlace theorem: Secondly, according to the definitionof the adjacency matrix of hypergraph, we obtain other results. The mainly results as fol-lows:Theorem3.1: Let H be a connected r-uniform linear hypergraph then(1) its largest eigenvalueλ1(>0) is a simple.(2) if x is an eigenvector forρ,then x is a positive eigenvector.(3) For any eigenvalueλ(=λ1),then ?λ1<λ<λ1.(4) If any hyperedge is deleted,then the largest eigenvalue will decrease.Theorem3.2: Let H = (E1,E2,···,Em) be a r-uniform linear hypergraph,λ1 >λ2≥···≥λn are the spectrum of H,μ1 >μ2≥···≥μn-1 are the spectrum of H ? v, thenλ1≥μ1≥λ2≥μ2≥···≥μn?1≥λn.Theorem3.3: Let A = (aij)n×n be the adjacency matrix of r-uniform linear hypergraphH,the number of chains of length l in H,from vi to vj,is the entry in position (i,j) of thematrix Al.Theorem3.4: If A is the adjacency of r-uniform linear hypergraph H. Letλ1,λ2,···,λn bethe eigenvalues of A and c be the number of closed chains of length k in H,from vi to vi.then Theorem3.5: Let H = (E1,E2,···,Em) be the connected r-uniform linear hypergraphof order n,the diameter of H is d(H) = d,then the number of distinct eigenvalues s satisfyn≥s≥d + 1.In the forth part:This part is made up of two sections, in the first section, we characterizethe spectral radius by rank r, the number of edges m , vertices n, the degree of the vertices,maximum degree ?, minimum degreeδ, the strong chromatic numberγ(H) and so on, Themainly results as follows:Theorem4.1: Let H = (E1,E2,···,Em) be a connected r-uniform linear hypergraphand d1,d2,···,dn be the degree of the vertices. Then m2r {vi,vj}∈Ekmax{ d1ivi～vj didj|vi∈V (H)}.Theorem4.2: Let H = (E1,E2,···,Em) be a r-uniform linear hypergraph andρ(H) itsspectral radius. Then (r ? 1)≤ρ(H)≤(r ? 1).Theorem3.3: Let H = (E1,E2,···,Em) be a r-uniform linear hypergraph and supposethatλ1 is the largest eigenvalue of H.Then mr(nr? 1)≤λ1≤mr(r?n1) (n?1).Theorem4.4: Letλ1≥λ2≥···≥λn are the spectrum of r-uniform linear hypergraph H,let k =γ(H).Thenρ(H)≤?(λn +λn?1 +···+λn?k+2).Theorem4.5: Let H = (E1,E2,···,Em) be a connected r-uniform linear hypergraph, Letρ(H) =λ1 >λ2≥···≥λn be the eigenvalues of H,Thenρ(H)≤mr(r?γ1)((Hγ)( H)?1).Theorem4.6: Let H = (E1,E2,···,Em) be a r-uniform linear hypergraph of order n,and lbe the least number satisfyingρ(H)≤?(λn+λn?1+···+λn?l+1).Thenρ(H)≤mrl(+r?1 1)l.Theorem4.7: Let H = (E1,E2,···,Em) be a connected r-uniform linear hypergraph withadjacency matrix A of order n,d1,d2,···,dn is the degree of the vertices.Thenρ(H)≤δ(r-1)-1+√[δ(r-1)2- 1]2+4(r-1)(rm-n).In the second section,we characterize the second eigenvalue of H,and obtain some results :Theorem4.8: Let H = (E1,E2,···,Em) be a r-uniform linear hypergraph with adjacencymatrix A = (aij)n×n ,and X be an eigenvector of H with respect to eigenvalueα<ρ(H).Let?n+,n? and n0 denote the number of positive,negative and zero entries in X.ThenCollary2: Let H = (E1,E2,···,Em) be a r-uniform linear hypergraph with n vertices.Then In the fifth part we introduce two formula about simplify characteristic polynomial and ob-tain some results:Theorem5.1: Let H = (E1,E2,···,Em) be hypergraph and E1 = {v1,v2,v3}. andd(v1) = d(v2) = 1,H1 = H- {v1},H2 = H - {v1,v2},H3 = H - {v1,v2,v3}.ThenPH(λ) = (λ2-1)PH2- 2(λ+ 1)PH3(λ).Theorem5.2: Let H1 and H2 are two linear hypergraph, H is obtained by joining a vertexv1 in H1 and a vertex v2 in H2 with a edge E of rank r,Let Hi is obtained by deleting vertexvi (i = 1,2) from Hi,i.e.Hi=Hi - {vi}. Then PH(λ) = (λ+ 1)r-3P(λ).Here P(λ) = [λ- (r- 3)][PH1(λ)PH2(λ) ? PH1(λ)PH2(λ)]- (r - 2)[PH1(λ)PH2(λ) +2PH1(λ)PH2(λ) + PH1(λ)PH2(λ)]Theorem5.3: Let H = (E1,E2,···,Em) be the connected r-uniform star hypergraph oforder n, and |Ei Ej| = {v1}(i = j), Then...