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σ<sub>k</sub>（G）=min{∑<sub&g...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σ<sub>k</sub>（G）=min{∑<sub>i</sub>=1<sup>k</sup> d（v<sub>i</sub>）|{v<sub>1</sub>, v<sub>2</sub>,…, v<sub>k</sub>} 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 agraph 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 iscalled a Hamiltonian graph if c（G）=n. H.A. Jung proved that every 1-tough graphwith order n≥11 and σ2≥n-4 is Hamiltonian. We generalize it further as follows: ifG is a 1-tough graph and σ3（G）≥n, then c（G）≥min {n,2NC2（G）+4}. Thus, theconjecture of D. Bauer, G. Fan and H.J. Veldman in [2] is completely solved.展开更多
基金A research supported by National Natural Science Foundation of China.
文摘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σ<sub>k</sub>（G）=min{∑<sub>i</sub>=1<sup>k</sup> d（v<sub>i</sub>）|{v<sub>1</sub>, v<sub>2</sub>,…, v<sub>k</sub>} 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 agraph 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 iscalled a Hamiltonian graph if c（G）=n. H.A. Jung proved that every 1-tough graphwith order n≥11 and σ2≥n-4 is Hamiltonian. We generalize it further as follows: ifG is a 1-tough graph and σ3（G）≥n, then c（G）≥min {n,2NC2（G）+4}. Thus, theconjecture of D. Bauer, G. Fan and H.J. Veldman in [2] is completely solved.
