On Toughness and Hamiltonicity of 2K2-Free Graphs
The toughness of a (noncomplete) graph G is the minimum value of t for which there is a vertex cut A whose removal yields components. Determining toughness is an NP-hard problem for general input graphs. The toughness conjecture of Chvtal, which states that there exists a constant t such that every graph on at least three vertices with toughness at least t is hamiltonian, is still open for general graphs. We extend some known toughness results for split graphs to the more general class of 2K2-free graphs, that is, graphs that do not contain two vertex-disjoint edges as an induced subgraph. We prove that the problem of determining toughness is polynomially solvable and that Chvtal's toughness conjecture is true for 2K2-free graphs.
toughness 2k2-free graphs split graphs hamilton cycle