The least eigenvalue of the graph

Gao RunxiaYu GuidongCai Gaixiang

(1.Department of Social Undertakings,Anqing Vocational and Technical College,Anqing 246133,China;2.School of Mathematics and Physics,Anqing Normal University,Anqing 246133,China)

Abstract：Let G be a simple graph.The adjacency matrix is denoted by G.The least eigenvalue of A(G),denoted by λmin(G),is called the least eigenvalue of G.In this paper we first establish the relations between the number of edges and the least eigenvalue of the adjacency matrix of the graph,and then give some spectral conditions for a graph having Hamiltonian paths or Hamiltonian cycles,or being Hamilton-connected,or being traceable from every vertex in terms of the least eigenvalue of the adjacency matrix of the graph.This provides an effective method for us to study some properties for a graph.

Keywords：least eigenvalue,Hamiltonian path,Hamiltonian cycle,Hamilton-connected graph

1 Introduction

LetG=(V,E)be a simple graph of ordernwith vertex set

and edge setE=E(G).LetKnbe the complete graph of ordern.WriteKn?1+vforKn?1together with an isolated vertex,Kn?1+eforKn?1with a pendent edge,andKn?1+e+e′obtained fromKn?1+vby adding two edges betweenvand two vertices ofKn?1.The join ofGandH,denotedG∨H,is the graph obtained from disjoint union ofGandHby adding edges joining every vertex ofGto every vertex ofH.

The degree matrix ofGis denoted byD(G)=diag(dG(v1),dG(v2),···,dG(vn)),wheredG(v)denotes the degree of a vertexvin the graphG.The adjacency matrix ofGis defined to be a matrixA(G)=[aij]of ordern,whereaij=1 ifviis adjacent tovj,andaij=0 otherwise.The signless Laplacian matrix ofGis defined by

Obviously,A(G),Q(G)are real symmetric matrix.So their eigenvalues are real number and can be ordered.The largest eigenvalue ofA(G),denoted byλ(G),is said to be the spectral radius ofG.The least eigenvalue ofA(G),denoted byλmin(G),is said to be the least eigenvalue ofG.The unit eigenvector according toλmin(G)is said to be the first eigenvector ofG.The largest eigenvalue ofQ(G),denoted byq(G),is said to be the signless Laplacian spectral radius ofG.

LetGbe a simple graph of ordern.A Hamiltonian cycle of the graphGis a cycle of orderncontained inG,and a Hamiltonian path ofGis a path of orderncontained inG.A graph is traceable from every vertex if it contains a Hamilton path from every vertex.A graph is said to be Hamiltonian if it contains Hamiltonian cycles,and is said to be Hamilton-connected if every two vertices ofGare connected by a Hamiltonian path.The problem of deciding whether a graph is Hamiltonian is one of the most difficult classical problems in graph theory.Indeed,determining whether a graph is Hamiltonian is NP-complete.

Recently,the spectral theory of graphs has been applied to this problem.Reference[1]gives sufficient conditions for a graph to be traceable or Hamiltonian in terms of the spectral radius of the adjacency matrix of the graph or its complements.Reference[2]investigates the spectral radius of the signless Laplacian matrix of the complements of a graph,and present some conditions for the existence of Hamiltonian paths or cycles.The work motivated further research,one may refer to References[3-7].Reference[8]gives some(signless Laplacian)radius spectral conditions for a graph to be Hamiltonconnected.

However,until now there are few results about characterization the Hamiltonicity of a graph by least eigenvalue.In this paper,we still study the Hamiltonicity of a graph.However,we use the least eigenvalue of the adjacency matrix of the graph,and give some conditions for a graph having Hamiltonian paths or cycles,or being Hamilton-connected,or being traceable from every vertex.

2 Main results