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 |A|/t 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 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 Chvátal's toughness conjecture is true for 2K2-free graphs.
Original language | Undefined |
---|---|
Pages (from-to) | 244-255 |
Number of pages | 12 |
Journal | Journal of graph theory |
Volume | 75 |
Issue number | 3 |
DOIs | |
Publication status | Published - Mar 2014 |
Keywords
- EWI-24563
- MSC-05C
- Forbidden subgraph
- Hamiltonian graph
- Toughness
- t-Tough graph
- METIS-305860
- IR-89614
- 2K2-free graph