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

Burzio, Marco; Demaria, Davide Carlo

Acta Univ. Carol., Math. Phys. 29, No. 2, 3-14 (1988).

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

Keywords:

cyclic characteristic; Hamiltonian tournament