×

On a classification of Hamiltonian tournaments. (English) Zbl 0679.05035

Let T be a tournament. Then cc(T), the cyclic characteristic of T, is the length of the shortest cycle \(C=v_ 1...v_ kv_ 1\) with the property: for each vertex \(v\in T-C\) there is at least one arc from v to C and at least one arc from C to v. The main result of the paper is that for each Hamiltonian tournament \(H_ n\) on n vertices, \(3\leq cc(H_ n)\leq n-2\), and for each \(n\geq 5\) and k, \(3\leq k\leq n-2\), there exists a Hamiltonian tournament with \(cc(H_ n)=k\).
Reviewer: P.Horak

MSC:

05C20 Directed graphs (digraphs), tournaments
05C45 Eulerian and Hamiltonian graphs
PDF BibTeX XML Cite
Full Text: EuDML