On hamiltonicity of 1-tough triangle-free graphs
| Main Authors: | Zheng, Wei; School of Mathematics and Statistics, Shandong Normal University, Jinan, Shandong, 250358, P.R.~China, Broersma, Hajo; Faculty of EEMCS, University of Twente, P.O. Box 217, 7500 AE Enschede, The Netherlands, Wang, Ligong; School of Mathematics and Statistics, Northwestern Polytechnical University, Xi'an, Shaanxi, 710129, P.R. China |
|---|---|
| Format: | Article info application/pdf eJournal |
| Bahasa: | eng |
| Terbitan: |
GTA Research Group, Univ. Newcastle, Indonesian Combinatorics Society and ITB
, 2021
|
| Subjects: | |
| Online Access: |
https://www.ejgta.org/index.php/ejgta/article/view/873 https://www.ejgta.org/index.php/ejgta/article/view/873/pdf_190 |
Daftar Isi:
- 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.