Toughness and forbidden subgraphs for hamiltonian-connected graphs

Wei Zheng, Hajo Broersma, Ligong Wang

Research output: Contribution to conferencePaperpeer-review

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 languageEnglish
Pages139-142
Number of pages4
Publication statusPublished - 2019
Event17th Cologne-Twente Workshop on Graphs and Combinatorial Optimization, CTW 2019 - U-Parkhotel, Enschede, Netherlands
Duration: 1 Jul 20193 Jul 2019
Conference number: 17
http://wwwhome.math.utwente.nl/~ctw/

Workshop

Workshop17th Cologne-Twente Workshop on Graphs and Combinatorial Optimization, CTW 2019
Abbreviated titleCTW 2019
Country/TerritoryNetherlands
CityEnschede
Period1/07/193/07/19
Internet address

Fingerprint

Dive into the research topics of 'Toughness and forbidden subgraphs for hamiltonian-connected graphs'. Together they form a unique fingerprint.

Cite this