✦ LIBER ✦

Hamiltonian paths and cycles in hypertournaments

✍ Scribed by Gutin, Gregory; Yeo, Anders

Publisher: John Wiley and Sons
Year: 1997
Tongue: English
Weight: 138 KB
Volume: 25
Category: Article
ISSN: 0364-9024
DOI: 10.1002/(sici)1097-0118(199708)25:4<277::aid-jgt5>3.0.co;2-h

No coin nor oath required. For personal study only.

✦ Synopsis

Given two integers n and k, n ≥ k > 1, a k-hypertournament T on n vertices is a pair (V, A), where V is a set of vertices, |V | = n and A is a set of k-tuples of vertices, called arcs, so that for any k-subset S of V, A contains exactly one of the k! k-tuples whose entries belong to S. A 2-hypertournament is merely an (ordinary

A cycle can be defined analogously. A path or cycle containing all vertices of T (as v i 's) is Hamiltonian. T is strong if T has a path from x to y for every choice of distinct x, y ∈ V . We prove that every k-hypertournament on n (>k) vertices has a Hamiltonian path (an extension of Redei's theorem on tournaments) and every strong k-hypertournament with n (>k + 1) vertices has a Hamiltonian cycle (an extension of Camion's theorem on tournaments). Despite the last result, it is shown that the Hamiltonian cycle problem remains polynomial time solvable only for k ≤ 3 and becomes NP-complete for every fixed integer k ≥ 4.

📜 SIMILAR VOLUMES

Edge-disjoint Hamiltonian cycles in hype

Edge-disjoint Hamiltonian cycles in hypertournaments

✍ Vojislav Petrovic; Carsten Thomassen 📂 Article 📅 2005 🏛 John Wiley and Sons 🌐 English ⚖ 58 KB

## Abstract We introduce a method for reducing __k__‐tournament problems, for __k__ ≥ 3, to ordinary tournaments, that is, 2‐tournaments. It is applied to show that a __k__‐tournament on __n__ ≥ k + 1 + 24__d__ vertices (when __k__ ≥ 4) or on __n__ ≥ 30__d__ + 2 vertices (when __k__ = 3) has __d__

A Parallel Reduction of Hamiltonian Cycl

A Parallel Reduction of Hamiltonian Cycle to Hamiltonian Path in Tournaments

✍ E. Bampis; M. Elhaddad; Y. Manoussakis; M. Santha 📂 Article 📅 1995 🏛 Elsevier Science 🌐 English ⚖ 393 KB

Closures, cycles, and paths

✍ Jochen Harant; Arnfried Kemnitz; Akira Saito; Ingo Schiermeyer 📂 Article 📅 2011 🏛 John Wiley and Sons 🌐 English ⚖ 104 KB

## Abstract In 1960 Ore proved the following theorem: Let __G__ be a graph of order __n__. If __d__(__u__) + __d__(__v__)≥__n__ for every pair of nonadjacent vertices __u__ and __v__, then __G__ is hamiltonian. Since then for several other graph properties similar sufficient degree conditions have

Hamiltonian cycles and paths with a pres

Hamiltonian cycles and paths with a prescribed set of edges in hypercubes and dense sets

✍ Rostislav Caha; V. Koubek 📂 Article 📅 2005 🏛 John Wiley and Sons 🌐 English ⚖ 275 KB 👁 1 views

## Abstract This paper studies techniques of finding hamiltonian paths and cycles in hypercubes and dense sets of hypercubes. This problem is, in general, easily solvable but here the problem was modified by the requirement that a set of edges has to be used in such path or cycle. The main result o

Hamilton Cycles and Paths in Fullerenes.

✍ Dragan Marusic 📂 Article 📅 2007 🏛 John Wiley and Sons ⚖ 11 KB

Chromatic Roots and Hamiltonian Paths

✍ C. Thomassen 📂 Article 📅 2000 🏛 Elsevier Science 🌐 English ⚖ 89 KB

We present a new connection between colorings and hamiltonian paths: If the chromatic polynomial of a graph has a noninteger root less than or equal to then the graph has no hamiltonian path. This result is best possible in the sense that it becomes false if t 0 is replaced by any larger number.