Toughness, Forbidden Subgraphs, and Hamilton-Connected Graphs

A graph G is called Hamilton-connected if for every pair of distinct vertices {u, v} of G there exists a Hamilton path in G that connects u and v. A graph G is said to be t-tough if t center dot omega(G - X) <= |X| for all X subset of V (G) with omega(G - X) > 1. The toughness of G, denoted tau (G), is the maximum value of t such that G is t-tough (taking tau (K-n) = infinity for all n >= 1). It is known that a Hamilton-connected graph G has toughness tau (G) > 1, but that the reverse statement does not hold in general. In this paper, we investigate all possible forbidden subgraphs H such that every H-free graph G with tau (G) > 1 is Hamilton-connected. We find that the results are completely analogous to the Hamiltonian case: every graph H such that any 1-tough H-free graph is Hamiltonian also ensures that every H-free graph with toughness larger than one is Hamilton-connected. And similarly, there is no other forbidden subgraph having this property, except possibly for the graph K-1 ? P-4 itself. We leave this as an open case.