Abstract
A graph G is called hamiltonian-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•w(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) = 1 for all n ≤ 1). It is known that a hamiltonian-connected graph G has toughness τ (G) > 1, but that the reverse statement does not hold in general. In this presentation, we investigate all possible forbidden subgraphs H such that every H-free graph G with τ(G) > 1 is hamiltonian-connected. Except for one open case H = K1 [ P4, we characterize all possible graphs H with this property.
Original language | English |
---|---|
Pages | 139-142 |
Number of pages | 4 |
Publication status | Published - 2019 |
Event | 17th Cologne-Twente Workshop on Graphs and Combinatorial Optimization, CTW 2019 - U-Parkhotel, Enschede, Netherlands Duration: 1 Jul 2019 → 3 Jul 2019 Conference number: 17 http://wwwhome.math.utwente.nl/~ctw/ |
Workshop
Workshop | 17th Cologne-Twente Workshop on Graphs and Combinatorial Optimization, CTW 2019 |
---|---|
Abbreviated title | CTW 2019 |
Country/Territory | Netherlands |
City | Enschede |
Period | 1/07/19 → 3/07/19 |
Internet address |