×

On Hamiltonicity of 1-tough triangle-free graphs. (English) Zbl 1482.05177

Summary: Let \(\omega (G)\) denote the number of components of a graph \(G\). A connected graph \(G\) is said to be 1-tough if \(\omega (G -X) \leq |X|\) for all \(X \subseteq V(G)\) with \(\omega (G -X)>1\). It is well-known that every hamiltonian graph is 1-tough, but that the reverse statement is not true in general, and even not for triangle-free graphs. We present two classes of triangle-free graphs for which the reverse statement holds, i.e., for which hamiltonicity and 1-toughness are equivalent. Our two main results give partial answers to two conjectures due to Nikoghosyan.

MSC:

05C38 Paths and cycles
05C42 Density (toughness, etc.)
05C45 Eulerian and Hamiltonian graphs
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Using Claim 10 and Claim 11, it is clear that there is a cycle in G containing all the vertices of G. Hence, G is hamiltonian. This completes the proof of Theorem 1.4.
[2] P. Bedrossian, Forbidden Subgraph and Minimum Degree Conditions for Hamiltonicity, The-sis, Memphis State University, USA, 1991.
[3] J.A. Bondy and U.S.R. Murty, Graph Theory, Springer Graduate Texts in Mathematics, vol. 244 (2008). · Zbl 1134.05001
[4] H.J. Broersma, V. Patel, and A. Pyatkin, On toughness and hamiltonicity of 2K 2 -free graphs, J. Graph Theory, 75 (2014) 244-255. · Zbl 1292.05162
[5] V. Chvátal, Tough graphs and hamiltonian circuits, Discrete Math., 5 (1973) 215-228. · Zbl 0256.05122
[6] M. Haythorpe and A. Johnson, Change ringing and Hamiltonian cycles: The search for Erin and Stedman triples, Electron. J. Graph Theory Appl., 7 (1) (2019) 61-75. · Zbl 1467.05146
[7] B. Li, H.J. Broersma, and S. Zhang, Forbidden subgraphs for traceability of block chains, Electron. J. Graph Theory Appl., 1 (1) (2013) 1-10. · Zbl 1306.05205
[8] B. Li, H.J. Broersma, and S. Zhang, Forbidden subgraphs for hamiltonicity of 1-tough graphs, Discuss. Math. Graph Theory, 36 (2016) 915-929. · Zbl 1350.05088
[9] Zh.G. Nikoghosyan, Disconnected forbidden subgraphs, toughness and hamilton cycles, ISRN Combinatorics, 2013, Article ID 673971 (2013) 4 pages. · Zbl 1264.05080
[10] S. Shan, Hamiltonian cycles in 3-tough 2K 2 -free graphs, J. of Graph Theory, 94 (2020) 349-363. · Zbl 1486.05172
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.