On Toughness and Hamiltonicity of 2K2‐Free Graphs |
| |
| Authors: | Hajo Broersma Viresh Patel Artem Pyatkin |
| |
| Affiliation: | 1. FACULTY OF EEMCS, UNIVERSITY OF TWENTE, AE ENSCHEDE, THE NETHERLANDS;2. SCHOOL OF MATHEMATICS, UNIVERSITY OF BIRMINGHAM, UNITED KINGDOM;3. SOBOLEV INSTITUTE OF MATHEMATICS, RUSSIA |
| |
| 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 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. |
| |
| Keywords: | toughness 2K2‐free graphs split graphs Hamilton cycle |
|
|
