Premium
Hamilton cycles, avoiding prescribed arcs, in close‐to‐regular tournaments
Author(s) -
Yeo Anders
Publication year - 1999
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/(sici)1097-0118(199910)32:2<123::aid-jgt3>3.0.co;2-y
Subject(s) - tournament , combinatorics , mathematics , digraph , multipartite , partition (number theory) , hamiltonian (control theory) , hamiltonian path , graph , discrete mathematics , physics , mathematical optimization , quantum mechanics , quantum entanglement , quantum
The local irregularity of a digraph D is defined as i l ( D ) = max {| d + ( x ) − d − ( x )| : x ϵ V ( D )}. Let T be a tournament, let Γ = { V 1 , V 2 , …, V c } be a partition of V ( T ) such that | V 1 | ≥ | V 2 | ≥ … ≥ | V c |, and let D be the multipartite tournament obtained by deleting all the arcs with both end points in the same set in Γ. We prove that, if | V ( T )| ≥ max{2 i l ( T ) + 2| V 1 | + 2| V 2 | − 2, i l ( T ) + 3| V 1 | − 1}, then D is Hamiltonian. Furthermore, if T is regular (i.e., i l ( T ) = 0), then we state slightly better lower bounds for | V ( T )| such that we still can guarantee that D is Hamiltonian. Finally, we show that our results are best possible. © 1999 John Wiley & Sons, Inc. J Graph Theory 32: 123–136, 1999