Tough graphs and Hamiltonian circuits. (Q2558871): Difference between revisions

A graph \(G\) is called \(t\)-tough if deletion of any \(s\) points from \(G\) results in a graph which is either connected or else has at most \(s/t\) components. The relationship between toughness and other graph-theoretical invariants is explored; for instance, the square of a \(k\)-connected graph is always \(k\)-tough. Clearly, every Hamiltonian graph is 1-tough. On the other hand the author conjectures that there is a \(t_0\), such that every \(t_0\)-tough graph is Hamiltonian. With \(t_0=2\), this conjecture would generalize a recent theorem of Fleischner (the square of a \(2\)-connected graph is Hamiltonian). The author constructs an infinite family of \(3/2\)-tough non-Hamiltonian graphs.