Name
Abstract | ||
|---|---|---|
A hypertournament or a k-tournament, on n vertices, 2≤k≤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 k 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 k≥8 and n≥k + 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, k≥4, and n≥k + 2, a strong k-tournament on n vertices 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 d edge-disjoint cycles of each possible length and extend strong connectivity to require d edge-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 |
Year | DOI | Venue |
|---|---|---|
2010 | 10.1002/jgt.v63:4 | Journal of Graph Theory |
Keywords | Field | DocType |
hypertournaments,Hamiltonian cycles | Graph theory,Discrete mathematics,Combinatorics,Vertex (geometry),Existential quantification,Permutation,If and only if,Mathematics | Journal |
Volume | Issue | ISSN |
63 | 4 | 0364-9024 |
Citations | PageRank | References |
4 | 0.70 | 1 |
Authors | ||
1 | ||