Toughness, hamiltonicity and split graphs

https://doi.org/10.1016/0012-365X(95)00190-8Get rights and content
Under an Elsevier user license
open archive

Abstract

Related to Chvátal's famous conjecture stating that every 2-tough graph is hamiltonian, we study the relation of toughness and hamiltonicity on special classes of graphs.

First, we consider properties of graph classes related to hamiltonicity, traceability and toughness concepts and display some algorithmic consequences. Furthermore, we present a polynomial time algorithm deciding whether the toughness of a given split graph is less than one and show that deciding whether the toughness of a bipartite graph is exactly one is coNP-complete.

We show that every 32-tough split graph is hamiltonian and that there is a sequence of non-hamiltonian split graphs with toughness converging to 32.

Cited by (0)

1

On leave from Computer and Automation Institute, Hungarian Academy of Science, H-1111 Budapest, Hungary.