Hamiltonian paths and cycles in hypertournaments

Abstract

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) tournament. A path is a sequence v1a1v2v3···vt-1vt of distinct vertices v1, v2,, vt and distinct arcs a1, , at-1 such that vi precedes vt-1 in a, 1 i t - 1. A cycle can be defined analogously. A path or cycle containing all vertices of T (as vi'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 Redeis theorem on tournaments) and every strong k-hypertournament with n (k + 1) vertices has a Hamiltonian cycle (an extension of Camions 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. © 1997 John Wiley & Sons, Inc. J Graph Theory 25: 277-286, 1997