An algorithmic approach to a conjecture of Chvátal on toughness and hamiltonicity of graphs

The main motivation for this project is to find a nonhamiltonian graph with toughness at least nine over four. This would improve the lower bound on t in the following conjecture by Chvatal: there exists a real number t such that every t-tough graph is hamiltonian [Chv73]. Secondly, we aim to research the open question whether the known nonhamiltonian 2-tough graph on 42 vertices is the smallest nonhamiltonian 2-tough graph [BBV00]. A third motivation is to analyse chordal graphs similarly. In contrast to the purely graph theoretical approach of the referenced papers, our approach is mainly algorithmic. However, it is based on the same construction that is used to construct nonhamiltonian graphs with toughness approaching nine over four from below, which can also be applied to chordal graphs. We apply this known construction on all possible nonisomorphic graphs up to a certain number of vertices, by designing and implementing an algorithm that can determine the hamiltonicity and toughness of the constructed graph. We also design and implement an evolutionary algorithm, with the same aim to generate suitable graphs to construct nonhamiltonian graphs with a high toughness. Our research aims to optimise the performance of these two algorithms.