𝔖 Bobbio Scriptorium
✦   LIBER   ✦

A sufficient condition for a semicomplete multipartite digraph to be Hamiltonian

✍ Scribed by Jørgen Bang-Jensen; Gregory Gutin; Jing Huang

Publisher
Elsevier Science
Year
1996
Tongue
English
Weight
670 KB
Volume
161
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

✦ Synopsis

A multipartite tournament is an orientation of a complete k-partite graph for some k >~ 2. A factor of a digraph D is a collection of vertex disjoint cycles covering all the vertices of D. We show that there is no degree of strong connectivity which together with the existence of a factor will guarantee that a multipartite tournament is Hamiltonian. Our main result is a sufficient condition for a multipartite tournament to be Hamiltonian. We show that this condition is general enough to provide easy proofs of many existing results on paths and cycles in multipartite tournaments. Using this condition, we obtain a best possible lower bound on the length of a longest cycle in any strongly connected multipartite tournament.

📜 SIMILAR VOLUMES

Sufficient conditions for a digraph to b
Sufficient conditions for a digraph to be Hamiltonian
✍ Bang-Jensen, J�rgen; Gutin, Gregory; Li, Hao 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 412 KB 👁 2 views

We describe a new type of sufficient condition for a digraph to be Hamiltonian. Conditions of this type combine local structure of the digraph with conditions on the degrees of nonadjacent vertices. The main difference from earlier conditions is that we do not require a degree condition on all pairs