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/

[1] D. Bauer, H.J. Broersma, J.P.M. van den Heuvel and H.J. Veldman, On Hamiltonian properties of 2-tough graphs, J. Graph Theory 18 (1994) 539–543. https://doi.org/10.1002/jgt.3190180602

[2] D. Bauer, H.J. Broersma and H.J. Veldman, Not every 2 -tough graph is Hamiltonian, Discrete Appl. Math. 99 (2000) 317–321. https://doi.org/10.1016/S0166-218X(99)00141-9

[3] D. Bauer, H.J. Broersma and E. Schmeichel, Toughness in graphs—A survey, Graphs Combin. 22 (2006) 1–35. https://doi.org/10.1007/s00373-006-0649-0

[4] J.A. Bondy and U.S.R. Murty, Graph Theory (Grad. Texts in Math. 244 Springer-Verlag, London, 2008).

[5] H.J. Broersma, How tough is toughness ?, Bull. Eur. Assoc. Theor. Comput. Sci. EATCS 117 (2015).

[6] G. Chen and R.J. Gould, Hamiltonian connected graphs involving forbidden subgraphs, Bull. Inst. Combin. Appl. 29 (2000) 25–32.

[7] V. Chvátal, Tough graphs and Hamiltonian circuits, Discrete Math. 5 (1973) 215–228. https://doi.org/10.1016/0012-365X(73)90138-6

[8] H.A. Jung, On a class of posets and the corresponding comparability graphs, J. Combin. Theory Ser. B 24 (1978) 125–133. https://doi.org/10.1016/0095-8956(78)90013-8

[9] D. Kratsch, J. Lehel and H. Müller, Toughness, Hamiltonicity and split graphs, Discrete Math. 150 (1996) 231–245. https://doi.org/10.1016/0012-365X(95)00190-8

[10] B. Li, H.J. Broersma and S. Zhang, Forbidden subgraphs for Hamiltonicity of 1- tough graphs, Discuss. Math. Graph Theory 36 (2016) 915–929. https://doi.org/10.7151/dmgt.1897

[11] M.M. Matthews and D.P. Sumner, Hamiltonian results in K1,3-free graphs, J. Graph Theory 8 (1984) 139–146. https://doi.org/10.1002/jgt.3190080116

[12] Zh.G. Nikoghosyan, Disconnected forbidden subgraphs, toughness and Hamilton cycles, ISRN Combinatorics 2013 (2013) 673971. https://doi.org/10.1155/2013/673971