On hamiltonicity of 1-tough triangle-free graphs

Wei Zheng (School of Mathematics and Statistics, Shandong Normal University, Jinan, Shandong, 250358, P.R.~China)
Hajo Broersma (Faculty of EEMCS, University of Twente, P.O. Box 217, 7500 AE Enschede, The Netherlands)
Ligong Wang (School of Mathematics and Statistics, Northwestern Polytechnical University, Xi'an, Shaanxi, 710129, P.R. China)

Electronic Journal of Graph Theory and Applications (EJGTA)
Vol 9, No 2 (2021): Electronic Journal of Graph Theory and Applications

Let ω(G) denote the number of components of a graph G. A connected graph G is said to be 1-tough if ω(G − X)≤|X| for all X ⊆ V(G) with ω(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.