Geodesic
Forbidden Subgraphs for Hamiltonicity of 1-Tough Graphs
Discussiones Mathematicae. Graph Theory, Tome 36 (2016) no. 4, pp. 915-929.

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

A graph G is said to be 1-tough if for every vertex cut S of G, the number of components of G − S does not exceed |S|. Being 1-tough is an obvious necessary condition for a graph to be hamiltonian, but it is not sufficient in general. We study the problem of characterizing all graphs H such that every 1-tough H-free graph is hamiltonian. We almost obtain a complete solution to this problem, leaving H = K1 ∪ P4 as the only open case.
Keywords: forbidden subgraph, 1-tough graph, H-free graph, hamiltonian graph 
@article{DMGT_2016_36_4_a11,
     author = {Li, Binlong and Broersma, Hajo J. and Zhang, Shenggui},
     title = {Forbidden {Subgraphs} for {Hamiltonicity} of {1-Tough} {Graphs}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {915--929},
     publisher = {mathdoc},
     volume = {36},
     number = {4},
     year = {2016},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2016_36_4_a11/}
}
TY  - JOUR
AU  - Li, Binlong
AU  - Broersma, Hajo J.
AU  - Zhang, Shenggui
TI  - Forbidden Subgraphs for Hamiltonicity of 1-Tough Graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2016
SP  - 915
EP  - 929
VL  - 36
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2016_36_4_a11/
LA  - en
ID  - DMGT_2016_36_4_a11
ER  - 
%0 Journal Article
%A Li, Binlong
%A Broersma, Hajo J.
%A Zhang, Shenggui
%T Forbidden Subgraphs for Hamiltonicity of 1-Tough Graphs
%J Discussiones Mathematicae. Graph Theory
%D 2016
%P 915-929
%V 36
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2016_36_4_a11/
%G en
%F DMGT_2016_36_4_a11
Li, Binlong; Broersma, Hajo J.; Zhang, Shenggui. Forbidden Subgraphs for Hamiltonicity of 1-Tough Graphs. Discussiones Mathematicae. Graph Theory, Tome 36 (2016) no. 4, pp. 915-929. http://geodesic.mathdoc.fr/item/DMGT_2016_36_4_a11/

[1] D. Bauer, H.J. Broersma, J. van den Heuvel and H.J. Veldman, Long cycles in graphs with prescribed toughness and minimum degree, Discrete Math. 141 (1995) 1-10. doi: 10.1016/0012-365X(93)E0204-H

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

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

[4] P. Bedrossian, Forbidden Subgraph and Minimum Degree Conditions for Hamiltonicity (Ph.D. Thesis, Memphis State University, 1991).

[5] J.A. Bondy and U.S.R. Murty, Graph Theory (Graduate Texts in Mathematics, Springer 244, 2008).

[6] H.J. Broersma, On some intriguing problems in hamiltonian graph theory-a survey, Discrete Math. 251 (2002) 47-69. doi: 10.1016/S0012-365X(01)00325-9

[7] H.J. Broersma, V. Patel, and A. Pyatkin, On toughness and hamiltonicity of 2K2-free graphs, J. Graph Theory 75 (2014) 244-255. doi: 10.1002/jgt.21734

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

[9] R.J. Faudree and R.J. Gould, Characterizing forbidden pairs for hamiltonian properties, Discrete Math. 173 (1997) 45-60. doi: 10.1016/S0012-365X(96)00147-1

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

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

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