PANCYCLIC ARCS IN HAMILTONIAN CYCLES OF HYPERTOURNAMENTS
2
조회
0
다운로드
0
인용
0
참고문헌
키워드
초록
A k-hypertournament H on n vertices, where 2 ≤ k ≤ n, is a pair H = (V,A), where V is the vertex set of H and A is a set of k-tuples of vertices, called arcs, such that for all subsets S ⊆ V with |S| = k, A contains exactly one permutation of S as an arc. Recently, Li et al. showed that any strong k-hypertournament H on n vertices, where 3 ≤ k ≤ n − 2, is vertex-pancyclic, an extension of Moon’s theorem for tournaments. In this paper, we prove the following generalization of another of Moon’s theorems: If H is a strong k-hypertournament on n vertices, where 3 ≤ k ≤ n−2, and C is a Hamiltonian cycle in H, then C contains at least three pancyclic arcs.
Abstract
A k-hypertournament H on n vertices, where 2 ≤ k ≤ n, is a pair H = (V,A), where V is the vertex set of H and A is a set of k-tuples of vertices, called arcs, such that for all subsets S ⊆ V with |S| = k, A contains exactly one permutation of S as an arc. Recently, Li et al. showed that any strong k-hypertournament H on n vertices, where 3 ≤ k ≤ n − 2, is vertex-pancyclic, an extension of Moon’s theorem for tournaments. In this paper, we prove the following generalization of another of Moon’s theorems: If H is a strong k-hypertournament on n vertices, where 3 ≤ k ≤ n−2, and C is a Hamiltonian cycle in H, then C contains at least three pancyclic arcs.
참고문헌 (11)
- P. Camion, , C. R. Acad. Sci. Paris, 249, pp.2151~2152 (1959)
- Q. Guo, "Out-arc pancyclicity of vertices in tournaments", Discrete Appl. Math, 158(9), pp.996~1005 (2010)
- G. Gutin, "Hamiltonian paths and cycles in hypertournaments", J. Graph Theory, 25(4), pp.277~286 (1997)
- P. Hall, "On representatives of subsets", J. London Math. Soc, 10, pp.26~30 (1935)
- H. Li, "On the vertex-pancyclicity of hypertournaments", Discrete Appl. Math, 161(16-17), pp.2749~2752 (2013)
- J. W. Moon, "On subtournaments of a tournament", Canad. Math. Bull, 9, pp.297~301 (1966)
- J. W. Moon, "On k-cyclic and pancyclic arcs in strong tournaments", J. Combin. Inform. System Sci, 19(3-4), pp.207~214 (1994)
- V. Petrovic, "Edge disjoint Hamiltonian cycles in hypertournaments", J. Graph Theory, (1), pp.49~52 (2006)
- L. Redei, "Ein kombinatorischer Satz", Acta Litt. Sci. Szeged, 7, pp.39~43 (1934)
- J. Yang, "Vertex-pancyclicity of hypertournaments", J. Graph Theory, 63, pp.338~348 (2009)
- A. Yeo, "The number of pancyclic arcs in a k-strong tournament", J. Graph Theory, 50(3), pp.212~219 (2005)