Integrability Of Graphs And Hoffman Graphs

This thesis focuses on the problem of graphs with smallest eigenvalue at least-3.In 1976,Cameron et al.showed that if a graph G with smallest eigenvalue at least-2 has strictly more than 36 vertices,then G is a generalized line graph,that is,there exists an integral matrix N such that the equality A+2I=NTN holds,where A is the adjacency matrix of G and I is the identity matrix.As a generalization of the concept of generalized line graphs,we have the concept of the s-integrable graphs.Given a positive integer s,a graph G with the adjacency matrix A and smallest eigenvalue ?min is said to be s-integrable,if there exists an integral matrix N such that the adjacency matrix A satisfies the following A+[-?min]I=1/sNTN.By this definition,we have that the generalized line graphs are the 1-integrable graphs with smallest eigenvalue at least-2.This thesis is organized as follows:In Chapter 1,we will define lattices,give the concept of the s-integrability of lat-tices,which was first introduced by Conway and Sloane,and reveal the relationship of the s-integrability between lattices and graphs.We will also illuminate that to study the s-integrability of lattices whose minimal vectors have norm 3,it is important to study the s-integrability of graphs with smallest eigenvalue at least-3.In Chapter 2,we will introduce our main tool Hoffman graphs,which were intro-duced by Woo and Neumaier in 1995 and developed by Kim,Koolen,Yang and Y.later.A collection of known knowledge about Hoffman graphs will be given there.In Chapter 3,we will focus on graphs with smallest eigenvalue at least-3 and sufficiently large minimal valency.As a consequence,we will show that such kind of graphs are s-integrable for any s? 2.Moreover,we point out a fact that there exists a real number ?<-3,such that for any real number ??(?,-3],there exists a constant f(?),such that if a graph G has smallest eigenvalue at least A and minimal valency at least f(?),then the smallest eigenvalue of G is at least-3.In Chapter 4,our object is the 1-integrable graphs with smallest eigenvalue at least-3.Consequently,we will give a description for these graphs.In particular,we deter-mine all of the 1-integrable trees with smallest eigenvalue at least-3.In Chapter 5,we will use Hoffman graphs to prove that the 2-clique extension of the(t×t)-grid is determined by its spectrum,if t is large enough.This shows anther application of Hoffman graphs.In the last chapter,we list our problems and conjectures for future discussions.