Hostname: page-component-74656f9884-54qdv Total loading time: 0 Render date: 2026-11-10T04:03:05.136Z Has data issue: false hasContentIssue false

Hamiltonian Cycles Avoiding Prescribed Arcs in Tournaments

Published online by Cambridge University Press:  01 September 1997

JØRGEN BANG-JENSEN
Affiliation:
Department of Mathematics and Computer Science, Odense University, Odense, Denmark (e-mail: jbj@imada.ou.dk, z.g.gutin@brunel.ac.uk, gyeo@imada.ou.dk)
GREGORY GUTIN
Affiliation:
Department of Mathematics and Computer Science, Odense University, Odense, Denmark (e-mail: jbj@imada.ou.dk, z.g.gutin@brunel.ac.uk, gyeo@imada.ou.dk)
ANDERS YEO
Affiliation:
Department of Mathematics and Computer Science, Odense University, Odense, Denmark (e-mail: jbj@imada.ou.dk, z.g.gutin@brunel.ac.uk, gyeo@imada.ou.dk)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

Thomassen [6] conjectured that if I is a set of k−1 arcs in a k-strong tournament T, then T−I has a Hamiltonian cycle. This conjecture was proved by Fraisse and Thomassen [3]. We prove the following stronger result. Let T=(V, A) be a k-strong tournament on n vertices and let X1, X2, [ctdot ], Xl be a partition of the vertex set V of T such that [mid ]X1[mid ][les ][mid ]X2[mid ][les ][ctdot ][les ][mid ]Xl[mid ]. If k[ges ][sum ]l−1i=1[lfloor][mid ]Xi[mid ]/2[rfloor]+[mid ]Xl[mid ], then T−∪li=1{xy∈A[ratio ]x, y∈Xi} has a Hamiltonian cycle. The bound on k is sharp.

Information

Type
Research Article
Copyright
1997 Cambridge University Press