On Toughness and Hamiltonicity of 2 K 2 ‐Free Graphs
Hajo J. Broersma, Viresh S. Patel, A. V. Pyatkin · Journal of Graph Theory · 2013
Abstract 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 Chvátal, 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 2 K 2 ‐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 Chvátal's toughness conjecture is true for 2 K 2 ‐free graphs.