Geodesic
Toughness, Forbidden Subgraphs, and Hamilton-Connected Graphs
Discussiones Mathematicae. Graph Theory, Tome 42 (2022) no. 1, pp. 187-196

Voir la notice de l'article provenant de la source Library of Science

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) gt; 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) gt; 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) gt; 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.
Keywords: toughness, forbidden subgraph, Hamilton-connected graph, Hamiltonicity 
@article{DMGT_2022_42_1_a11,
     author = {Zheng, Wei and Broersma, Hajo and Wang, Ligong},
     title = {Toughness, {Forbidden} {Subgraphs,} and {Hamilton-Connected} {Graphs}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {187--196},
     publisher = {mathdoc},
     volume = {42},
     number = {1},
     year = {2022},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2022_42_1_a11/}
}
TY  - JOUR
AU  - Zheng, Wei
AU  - Broersma, Hajo
AU  - Wang, Ligong
TI  - Toughness, Forbidden Subgraphs, and Hamilton-Connected Graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2022
SP  - 187
EP  - 196
VL  - 42
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2022_42_1_a11/
LA  - en
ID  - DMGT_2022_42_1_a11
ER  - 
%0 Journal Article
%A Zheng, Wei
%A Broersma, Hajo
%A Wang, Ligong
%T Toughness, Forbidden Subgraphs, and Hamilton-Connected Graphs
%J Discussiones Mathematicae. Graph Theory
%D 2022
%P 187-196
%V 42
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2022_42_1_a11/
%G en
%F DMGT_2022_42_1_a11
Zheng, Wei; Broersma, Hajo; Wang, Ligong. Toughness, Forbidden Subgraphs, and Hamilton-Connected Graphs. Discussiones Mathematicae. Graph Theory, Tome 42 (2022) no. 1, pp. 187-196. http://geodesic.mathdoc.fr/item/DMGT_2022_42_1_a11/