Spectral analogues of Erdős’ theorem on Hamilton-connected graphs

摘要

A graph G is Hamilton-connected if for any pair of vertices v and w, G has a spanning (v, w)-path. Extending theorems of Dirac and Ore, Erdős prove a sufficient condition in terms of minimum degree and the size of G to assure G to be Hamiltonian. We investigate the spectral analogous of Erdős’ theorem for a Hamilton-connected graph with given minimum degree, and prove that there exist two graphs {Lnk,Mnk} such that each of the following holds for an integer k ≥ 3 and a simple graph G on n vertices.(i) If n ≥ 6k, δ(G) ≥ k, and |E(G)|>(n−k2)+k(k+1), then G is Hamilton-connected if and only if Cn+1(G)∉{Lnk,Mnk}.(ii) If n≥max{6k,12k3−12k2+k+4}, δ(G) ≥ k and spectral radius λ(G)≥n−k, then G is Hamilton–connected if and only if G∉{Lnk,Mnk}.