LI Jianping;TIAN Feng;SHEN Ruqun
Journal of Systems Science and Complexity. 1993, 6(1): 52-060.
Let G be a graph of order n. We define the distance between two vertices u andv in G, denoted by d(u, v), as the minimum value of the lengths of all u-v paths. We write σ_k(G)=min{∑_i=1~k d(v_i)|{v_1, v_2,…, v_k} is an independent set in G} and NC2(G)=min {|N(u)∪N(v)| | d(u, v)=2}. We denote by ω(G) the number of components of a graph G. A graph G is called 1-tough if ω(G\S)≤|S| for every subset S of V(G) withω(G\S)>l. By c(G) we denote the length of the longest cycle in G; in particular, G is called a Hamiltonian graph if c(G)=n. H.A. Jung proved that every 1-tough graph with order n≥11 and σ2≥n-4 is Hamiltonian. We generalize it further as follows: if G is a 1-tough graph and σ3(G)≥n, then c(G)≥min {n,2NC2(G)+4}. Thus, the conjecture of D. Bauer, G. Fan and H.J. Veldman in [2] is completely solved.
