On toughness and hamiltonicity of 2K2-free graphs

Haitze J. Broersma, Viresh Patel, Artem Pyatkin

Research output: Contribution to journal › Article › Academic › peer-review

4 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

Broersma, Haitze J. ; Patel, Viresh ; Pyatkin, Artem. / On toughness and hamiltonicity of 2K2-free graphs. In: Journal of graph theory. 2014 ; Vol. 75, No. 3. pp. 244-255.
@article{1f432ca2587e4e8fb7153721ba033df4,
title = "On toughness and hamiltonicity of 2K2-free graphs",
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{\'a}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{\'a}tal's toughness conjecture is true for 2K2-free graphs.",
keywords = "EWI-24563, MSC-05C, Forbidden subgraph, Hamiltonian graph, Toughness, t-Tough graph, METIS-305860, IR-89614, 2K2-free graph",
author = "Broersma, {Haitze J.} and Viresh Patel and Artem Pyatkin",
note = "eemcs-eprint-24563",
year = "2014",
month = "3",
doi = "10.1002/jgt.21734",
language = "Undefined",
volume = "75",
pages = "244--255",
journal = "Journal of graph theory",
issn = "0364-9024",
publisher = "Wiley-Liss Inc.",
number = "3",

}

Broersma, HJ, Patel, V & Pyatkin, A 2014, 'On toughness and hamiltonicity of 2K2-free graphs' Journal of graph theory, vol. 75, no. 3, pp. 244-255. https://doi.org/10.1002/jgt.21734

On toughness and hamiltonicity of 2K2-free graphs. / Broersma, Haitze J.; Patel, Viresh; Pyatkin, Artem.

In: Journal of graph theory, Vol. 75, No. 3, 03.2014, p. 244-255.

Research output: Contribution to journal › Article › Academic › peer-review

TY - JOUR

T1 - On toughness and hamiltonicity of 2K2-free graphs

AU - Broersma, Haitze J.

AU - Patel, Viresh

AU - Pyatkin, Artem

N1 - eemcs-eprint-24563

PY - 2014/3

Y1 - 2014/3

N2 - 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.

AB - 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.

KW - EWI-24563

KW - MSC-05C

KW - Forbidden subgraph

KW - Hamiltonian graph

KW - Toughness

KW - t-Tough graph

KW - METIS-305860

KW - IR-89614

KW - 2K2-free graph

U2 - 10.1002/jgt.21734

DO - 10.1002/jgt.21734

M3 - Article

VL - 75

SP - 244

EP - 255

JO - Journal of graph theory

JF - Journal of graph theory

SN - 0364-9024

IS - 3

ER -

Broersma HJ, Patel V, Pyatkin A. On toughness and hamiltonicity of 2K2-free graphs. Journal of graph theory. 2014 Mar;75(3):244-255. https://doi.org/10.1002/jgt.21734

Access to Document