HAMILTONIAN PATHS AND CYCLES IN HYPERTOURNAMENTS

Given two integers n and k, n greater than or equal to k > 1, a k-hype rtournament T on n vertices is a pair (V, A), where V is a set of vert ices, \V\ = n and A is a set of k-tuples of vertices, called arcs, so that for any k-subset S oi V, A contains exactly one of the k! k-tuple s whose entries belong to S. A 2-hypertournament is merely an (ordinar y) tournament. A path is a sequence v(1)a(1)v(2)a(2)v(3)...v(t-1)a(t-1 )v(t) of distinct vertices v(1), v(2),...,v(t) and distinct arcs a(1), ...,a(t-1) such that v(i) precedes v(i+1) in a(i), 1 less than or equa l to i less than or equal to t - 1. A cycle can be defined analogously A path or cycle containing all vertices of T (as v(i)'s) is Hamiltoni an. T is strong if T has a path from x to y for every choice of distin ct x, y is an element of V. We prove that every k-hypertournament on n (> k) vertices has a Hamiltonian path (an extension of Redei's theore m 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 Hamiltonia n cycle problem remains polynomial time solvable only for k less than or equal to 3 and becomes NP-complete for every fixed integer k greate r than or equal to 4. (C) 1997 John Wiley & Sons, Inc.