On hamiltonian‐connected graphs

One of the most fundamental results concerning paths in graphs is due to Ore: In a graph G , if deg x + deg y ≧ | V ( G )| + 1 for all pairs of nonadjacent vertices x, y ≅ V ( G ), then G is hamiltonian‐connected. We generalize this result using set degrees. That is, for S ⊂ V ( G ), let deg S = | x≅S N ( x )|, where N ( x ) = { v | xv ≅ E ( G )} is the neighborhood of x . In particular we show: In a 3‐connected graph G , if deg S 1 + deg S 2 ≧ | V ( G )| + 1 for each pair of distinct 2‐sets of vertices S 1 , S 2 ⊂ V ( G ), then G is hamiltonian‐connected. Several corollaries and related results are also discussed.