Hamiltonian Properties of 2-Tough Graphs

摘要

A study on Hamiltonian properties of 2-tough graphs is presented. A graph G isHamiltonian if it contains a Hamilton cycle (a cycle containing every vertex of G); G is Hamiltonian connected if for every pair of distinct vertices x and y of G there is a Hamilton path (a path containing every vertex of G) with end vertices x and y. A well known conjecture in Hamiltonian graph theory states that every 2-tough graph is Hamiltonian. Some equivalent conjectures, for example the conjecture that every 2-tough graph is Hamiltonian connected, are given.