University of Twente Student Theses
An algorithmic approach to a conjecture of Chvátal on toughness and hamiltonicity of graphs
Kemp, Tim (2020) An algorithmic approach to a conjecture of Chvátal on toughness and hamiltonicity of graphs.
|
PDF
1MB |
| Abstract: | 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 Chvátal: 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. |
| Item Type: | Essay (Master) |
| Faculty: | EEMCS: Electrical Engineering, Mathematics and Computer Science |
| Subject: | 54 computer science |
| Programme: | Computer Science MSc (60300) |
| Link to this item: | https://purl.utwente.nl/essays/82685 |
| Export this item as: | BibTeX EndNote HTML Citation Reference Manager |
Show download statistics for this publication
Show download statistics for this publicationRepository Staff Only: item control page