Abstract:

A graph  G is a strong -［s,t］ graph if there are at least t independent edges in every included subgraph of s vertices. This paper proves that if  G  is a  k-connected strong -［k+4,2］ graph with  δ≥k+1, then G has a Hamilton path or is isomorphic to (∪^k+2_i=1H_i)∨G_k,where H_i≌K₂,i=1,2…k+2，and G_k is an arbitrary graph of k vertices.

Key words: strong -［s,t］ graph, Hamilton path, k-connected graphs