TY - JOUR

T1 - Vertex-pancyclicity of hypertournaments

AU - Yang, Jed

PY - 2010/4

Y1 - 2010/4

N2 - A hypertournament or a k-tournament, on n vertices, 2≤κ≤n, is a pair T=(V,E), where the vertex set V is a set of size n and the edge set E is the collection of all possible subsets of sizeκ of 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 u to v for each pair of distinct vertices u and 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 κ≥8 and n≥κ+3, then a k-tournament on n vertices 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,κ≥4, and n≥κ+2, a strong k-tournament on n vertices is pancyclic if and only if it is strong. The bound n≥κ+2 is tight. We also find bounds for the generalized problem when we extend vertex-pancyclicity to require d edge-disjoint cycles of each possible length and extend strong connectivity to require d edge-disjointpaths between each pair of vertices. Our results include and extend those of Petrovic and Thomassen.

AB - A hypertournament or a k-tournament, on n vertices, 2≤κ≤n, is a pair T=(V,E), where the vertex set V is a set of size n and the edge set E is the collection of all possible subsets of sizeκ of 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 u to v for each pair of distinct vertices u and 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 κ≥8 and n≥κ+3, then a k-tournament on n vertices 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,κ≥4, and n≥κ+2, a strong k-tournament on n vertices is pancyclic if and only if it is strong. The bound n≥κ+2 is tight. We also find bounds for the generalized problem when we extend vertex-pancyclicity to require d edge-disjoint cycles of each possible length and extend strong connectivity to require d edge-disjointpaths between each pair of vertices. Our results include and extend those of Petrovic and Thomassen.

KW - Hamiltonian cycles

KW - Hypertournaments

UR - http://www.scopus.com/inward/record.url?scp=77950196218&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=77950196218&partnerID=8YFLogxK

U2 - 10.1002/jgt.20432

DO - 10.1002/jgt.20432

M3 - Article

AN - SCOPUS:77950196218

VL - 63

SP - 338

EP - 348

JO - Journal of Graph Theory

JF - Journal of Graph Theory

SN - 0364-9024

IS - 4

ER -