Toughness, forbidden subgraphs, and Hamiltonian-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 ·ω(G−X) ≤ |X| for all X ⊆ V (G) with ω(G−X) > 1. The toughness of G, denoted τ(G), is the maximum value of t such that G is t-tough (taking τ(Kn) =∞ for all n ≥ 1). It is known that a Hamilton-connected graph G has toughness τ(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 τ(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 K1 ∪ P4 itself. We leave this as an open case. Supported by the National Natural Science Foundation of China (No. 11871398), the Natural Science Basic Research Plan in Shaanxi Province of China (No. 2018JM1032) and the China Scholarship Council (No. 201706290168). Corresponding author. 2 W. Zheng, H. Broersma and L. Wang