On hamiltonicity of 1-tough triangle-free graphs
Abstract
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.
Keywords
Full Text:
PDFDOI: http://dx.doi.org/10.5614/ejgta.2021.9.2.15
References
P. Bedrossian, Forbidden Subgraph and Minimum Degree Conditions for Hamiltonicity, Thesis, Memphis State University, USA, 1991.
J.A. Bondy and U.S.R. Murty, Graph Theory, Springer Graduate Texts in Mathematics, vol. 244 (2008).
H.J. Broersma, V. Patel, and A. Pyatkin, On toughness and hamiltonicity of 2K2-free graphs, J. Graph Theory, 75 (2014) 244–255.
V. Chvatal, Tough graphs and hamiltonian circuits, Discrete Math., 5 (1973) 215–228.
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.
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.
B. Li, H.J. Broersma, and S. Zhang, Forbidden subgraphs for hamiltonicity of 1-tough graphs, Discuss. Math. Graph Theory, 36 (2016) 915–929.
Zh.G. Nikoghosyan, Disconnected forbidden subgraphs, toughness and hamilton cycles, ISRN Combinatorics, 2013, Article ID 673971 (2013) 4 pages.
S. Shan, Hamiltonian cycles in 3-tough 2K2-free graphs, J. of Graph Theory, 94 (2020) 349–363.
Refbacks
- There are currently no refbacks.
ISSN: 2338-2287
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.