## Abstract

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 τ (K_{n}) = ∞ 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 K_{1} ? P_{4} itself. We leave this as an open case.

Original language | English |
---|---|

Journal | Discussiones Mathematicae - Graph Theory |

DOIs | |

Publication status | Accepted/In press - 30 Aug 2019 |

## Keywords

- forbidden subgraph
- Hamilton-connected graph
- Hamiltonicity
- toughness
- UT-Gold-D