Hamiltonicity of 3-tough (K₂ \cup 3K₁)-free graphs

MaRDI QIDQ6370177zbMATH OpenFDO

Authors Andrew Hatfield, Elizabeth Grimm

Publication date 13 June 2021

Abstract: Chv'{a}tal conjectured in 1973 the existence of some constant $t$ such that all $t$-tough graphs with at least three vertices are hamiltonian. While the conjecture has been proven for some special classes of graphs, it remains open in general. We say that a graph is $(K_{2}cup3K_1)$-free if it contains no induced subgraph isomorphic to $K_{2}cup3K_1$, where $K_{2}cup3K_1$ is the disjoint union of an edge and three isolated vertices. In this paper, we show that every 3-tough $(K_{2}cup3K_1)$-free graph with at least three vertices is hamiltonian.

This page was built for publication: Hamiltonicity of 3-tough $(K_2 \cup 3K_1)$-free graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6370177)