Vertex‐pancyclicity of hypertournaments

A hypertournament or a k‐tournament, on nvertices, 2≤k≤n, is a pair T=(V, E), where the vertex set Vis a set of size nand the edge set Eis the collection of all possible subsets of size kof V, called the edges, each taken in one of its k! possible permutations. A k‐tournament is pancyclic if there exists (directed) cycles of all possible lengths; it is vertex‐pancyclic if moreover the cycles can be found through any vertex. A k‐tournament is strong if there is a path from uto vfor each pair of distinct vertices uand v. A question posed by Gutin and Yeo about the characterization of pancyclic and vertex‐pancyclic hypertournaments is examined in this article. We extend Moon's Theorem for tournaments to hypertournaments. We prove that if k≥8 and n≥k+ 3, then a k‐tournament on nvertices is vertex‐pancyclic if and only if it is strong. Similar results hold for other values of k. We also show that when n≥7, k≥4, and n≥k+ 2, a strong k‐tournament on nvertices is pancyclic if and only if it is strong. The bound n≥k+ 2 is tight. We also find bounds for the generalized problem when we extend vertex‐pancyclicity to require dedge‐disjoint cycles of each possible length and extend strong connectivity to require dedge‐disjoint paths between each pair of vertices. Our results include and extend those of Petrovic and Thomassen. © 2009 Wiley Periodicals, Inc. J Graph Theory 63: 338–348, 2010