Premium
On hamiltonian‐connected graphs
Author(s) -
Gould Ronald J.,
Yu Xingxing
Publication year - 1994
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.3190180808
Subject(s) - combinatorics , mathematics , hamiltonian (control theory) , graph , connectivity , hamiltonian path , bound graph , discrete mathematics , graph power , line graph , mathematical optimization
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.