### Abstract

Original language | Undefined |
---|---|

Place of Publication | Enschede |

Publisher | Universiteit Twente |

Number of pages | 15 |

ISBN (Print) | 0169-2690 |

Publication status | Published - 1999 |

### Publication series

Name | Memorandum / Faculty of Mathematical Sciences |
---|---|

Publisher | Department of Applied Mathematics, University of Twente |

No. | 1499 |

ISSN (Print) | 0169-2690 |

### Keywords

- MSC-05C38
- EWI-3319
- IR-65687
- METIS-141297
- MSC-68R10

### Cite this

*Polynomial algorithms that prove an NP-hard hypothesis implies an NP-hard conclusion*. (Memorandum / Faculty of Mathematical Sciences; No. 1499). Enschede: Universiteit Twente.

}

*Polynomial algorithms that prove an NP-hard hypothesis implies an NP-hard conclusion*. Memorandum / Faculty of Mathematical Sciences, no. 1499, Universiteit Twente, Enschede.

**Polynomial algorithms that prove an NP-hard hypothesis implies an NP-hard conclusion.** / Bauer, D.; Broersma, Haitze J.; Morgana, A.; Schmeichel, E.

Research output: Book/Report › Report › Professional

TY - BOOK

T1 - Polynomial algorithms that prove an NP-hard hypothesis implies an NP-hard conclusion

AU - Bauer, D.

AU - Broersma, Haitze J.

AU - Morgana, A.

AU - Schmeichel, E.

N1 - Imported from MEMORANDA

PY - 1999

Y1 - 1999

N2 - A number of results in Hamiltonian graph theory are of the form $\mathcal{P}$$_{1}$ implies $\mathcal{P}$$_{2}$, where $\mathcal{P}$$_{1}$ is a property of graphs that is NP-hard and $\mathcal{P}$$_{2}$ is a cycle structure property of graphs that is also NP-hard. Such a theorem is the well-known Chv\'{a}tal-Erd\"{o}s Theorem, which states that every graph $G$ with $\alpha \leq \kappa $ is Hamiltonian. Here $\kappa $ is the vertex connectivity of $G$ and $\alpha $ is the cardinality of a largest set of independent vertices of $G$. In another paper Chv\'{a}tal points out that the proof of this result is in fact a polynomial time construction that either produces a Hamilton cycle or a set of more than $\kappa $ independent vertices. In this note we point out that other theorems in Hamiltonian graph theory have a similar character. In particular, we present a constructive proof of the well-known theorem of Jung for graphs on $16$ or more vertices..

AB - A number of results in Hamiltonian graph theory are of the form $\mathcal{P}$$_{1}$ implies $\mathcal{P}$$_{2}$, where $\mathcal{P}$$_{1}$ is a property of graphs that is NP-hard and $\mathcal{P}$$_{2}$ is a cycle structure property of graphs that is also NP-hard. Such a theorem is the well-known Chv\'{a}tal-Erd\"{o}s Theorem, which states that every graph $G$ with $\alpha \leq \kappa $ is Hamiltonian. Here $\kappa $ is the vertex connectivity of $G$ and $\alpha $ is the cardinality of a largest set of independent vertices of $G$. In another paper Chv\'{a}tal points out that the proof of this result is in fact a polynomial time construction that either produces a Hamilton cycle or a set of more than $\kappa $ independent vertices. In this note we point out that other theorems in Hamiltonian graph theory have a similar character. In particular, we present a constructive proof of the well-known theorem of Jung for graphs on $16$ or more vertices..

KW - MSC-05C38

KW - EWI-3319

KW - IR-65687

KW - METIS-141297

KW - MSC-68R10

M3 - Report

SN - 0169-2690

T3 - Memorandum / Faculty of Mathematical Sciences

BT - Polynomial algorithms that prove an NP-hard hypothesis implies an NP-hard conclusion

PB - Universiteit Twente

CY - Enschede

ER -