On toughness and hamiltonicity of 2K2-free graphs

Haitze J. Broersma, Viresh Patel, Artem Pyatkin

Research output: Contribution to journalArticleAcademicpeer-review

5 Citations (Scopus)

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 languageUndefined
Pages (from-to)244-255
Number of pages12
JournalJournal of graph theory
Volume75
Issue number3
DOIs
Publication statusPublished - Mar 2014

Keywords

  • EWI-24563
  • MSC-05C
  • Forbidden subgraph
  • Hamiltonian graph
  • Toughness
  • t-Tough graph
  • METIS-305860
  • IR-89614
  • 2K2-free graph

Cite this