Toughness, Forbidden Subgraphs, and Hamilton-Connected Graphs

Wei Zheng, Hajo Broersma*, Ligong Wang

*Corresponding author for this work

Research output: Contribution to journalArticleAcademicpeer-review

1 Citation (Scopus)

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 τ (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.

Original languageEnglish
JournalDiscussiones Mathematicae - Graph Theory
DOIs
Publication statusAccepted/In press - 30 Aug 2019

Keywords

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

Fingerprint

Dive into the research topics of 'Toughness, Forbidden Subgraphs, and Hamilton-Connected Graphs'. Together they form a unique fingerprint.

Cite this