Hamilton cycles, avoiding prescribed arcs, in close-to-regular tournaments

Anders Yeo

doi:10.1002/(SICI)1097-0118(199910)32:2<123::AID-JGT3>3.0.CO;2-Y

Hamilton cycles, avoiding prescribed arcs, in close-to-regular tournaments

Anders Yeo

University of Southern Denmark

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

4 Citations (Scopus)

Abstract

The local irregularity of a digraph D is defined as i_l(D) = max {|d⁺(cursive Greek chi)-d^-(cursive Greek chi)\ : cursive Greek chi ∈ V (D)}. Let T be a tournament, let Γ = {V₁, V₂,..., V_c} be a partition of V (T) such that |V₁| ≥ |V₂| ≥ ... ≥ |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{2i_l(T) + 2|V₁| + 2|V₂| -2, i_l(T) + 3|V₁|-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.

Original language	English
Pages (from-to)	123-136
Number of pages	14
Journal	Journal of Graph Theory
Volume	32
Issue number	2
DOIs	https://doi.org/10.1002/(SICI)1097-0118(199910)32:2<123::AID-JGT3>3.0.CO;2-Y
Publication status	Published - Oct 1999
Externally published	Yes

Keywords

Hamilton cycle
Irregularity regular
Multipartite tournament
Tournament

ASJC Scopus subject areas

Geometry and Topology

Access to Document

10.1002/(SICI)1097-0118(199910)32:2<123::AID-JGT3>3.0.CO;2-Y

Cite this

@article{7cab643f715f4ae98d4e3cfc2ea1c078,

title = "Hamilton cycles, avoiding prescribed arcs, in close-to-regular tournaments",

abstract = "The local irregularity of a digraph D is defined as il(D) = max \{|d+(cursive Greek chi)-d-(cursive Greek chi)\textbackslash{} : cursive Greek chi ∈ V (D)\}. Let T be a tournament, let Γ = \{V1, V2,..., Vc\} be a partition of V (T) such that |V1| ≥ |V2| ≥ ... ≥ |Vc| , 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 \textbackslash{}V(T)\textbackslash{} ≥ max\{2il(T) + 2|V1| + 2|V2| -2, il(T) + 3|V1|-1\}, then D is Hamiltonian. Furthermore, if T is regular (i.e., il(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.",

keywords = "Hamilton cycle, Irregularity regular, Multipartite tournament, Tournament",

author = "Anders Yeo",

year = "1999",

month = oct,

doi = "10.1002/(SICI)1097-0118(199910)32:2<123::AID-JGT3>3.0.CO;2-Y",

language = "English",

volume = "32",

pages = "123--136",

journal = "Journal of Graph Theory",

issn = "0364-9024",

publisher = "Wiley-Liss Inc.",

number = "2",

}

TY - JOUR

T1 - Hamilton cycles, avoiding prescribed arcs, in close-to-regular tournaments

AU - Yeo, Anders

PY - 1999/10

Y1 - 1999/10

N2 - The local irregularity of a digraph D is defined as il(D) = max {|d+(cursive Greek chi)-d-(cursive Greek chi)\ : cursive Greek chi ∈ V (D)}. Let T be a tournament, let Γ = {V1, V2,..., Vc} be a partition of V (T) such that |V1| ≥ |V2| ≥ ... ≥ |Vc| , 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{2il(T) + 2|V1| + 2|V2| -2, il(T) + 3|V1|-1}, then D is Hamiltonian. Furthermore, if T is regular (i.e., il(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.

AB - The local irregularity of a digraph D is defined as il(D) = max {|d+(cursive Greek chi)-d-(cursive Greek chi)\ : cursive Greek chi ∈ V (D)}. Let T be a tournament, let Γ = {V1, V2,..., Vc} be a partition of V (T) such that |V1| ≥ |V2| ≥ ... ≥ |Vc| , 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{2il(T) + 2|V1| + 2|V2| -2, il(T) + 3|V1|-1}, then D is Hamiltonian. Furthermore, if T is regular (i.e., il(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.

KW - Hamilton cycle

KW - Irregularity regular

KW - Multipartite tournament

KW - Tournament

UR - https://www.scopus.com/pages/publications/0033414534

U2 - 10.1002/(SICI)1097-0118(199910)32:2<123::AID-JGT3>3.0.CO;2-Y

DO - 10.1002/(SICI)1097-0118(199910)32:2<123::AID-JGT3>3.0.CO;2-Y

M3 - Article

AN - SCOPUS:0033414534

SN - 0364-9024

VL - 32

SP - 123

EP - 136

JO - Journal of Graph Theory

JF - Journal of Graph Theory

IS - 2

ER -

Hamilton cycles, avoiding prescribed arcs, in close-to-regular tournaments

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this