Gutin, Gregory and Yeo, A. (1997) Hamiltonian paths and cycles in hypertournaments. Journal of Graph Theory, 25 (4).
Full text access: Open
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
This is a Submitted version This version's date is: 1997 This item is not peer reviewed
https://repository.royalholloway.ac.uk/items/47cfd253-2bc8-1fcf-faa2-1fa7f09ac1a2/6/
Deposited by Research Information System (atira) on 03-Jul-2014 in Royal Holloway Research Online.Last modified on 03-Jul-2014