2013/02/19 by Hajo Broersma, Viresh Patel, A. V. Pyatkin · 1 citation
Computer Science · Mathematics · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Limits and Structures in Graph Theory
paper · doi:10.1002/jgt.21734
openalex publication_date 2013/02/19 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/02
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.