On the existence of specified cycles in a tournament

✍ Scribed by Abdelhamid Benhocine; A. Pawel Wojda

• Publisher: John Wiley and Sons
• Year: 1983
• Tongue: English
• Weight: 241 KB
• Volume: 7
• Category: Article
• ISSN: 0364-9024
• DOI: 10.1002/jgt.3190070413

✦ Synopsis

For 2 s p s n and n 2 3, D(n, p) denotes the digraph with n vertices obtained from a directed cycle of length n by changing the orientation of p -1 consecutives edges. In this paper, we prove that every tournament of order n 2 7 contains D(n, p ) for p = 2, 3, ..., n. Furthermore, we determine the tournaments of order n, 3 s n S 6, which do not contain D(n, p) for some p.

A tournament T of order n is a digraph on n vertices in which every pair of distinct vertices is joined by one edge. We use the standard terminology of Berge [3]. E(T) = E denotes the set of edges and V(T) = V the set of vertices of T. A partition ( A , B ) of V , A , and B written in this order is a directed cocycle if every edge joining A and B is oriented from A to B.

We know that a tournament T is strong if and only if it contains a directed Hamiltonian cycle and T is not strong if and only if it contains a directed cocycle.

Let n, p be two integers, n 5 3, 2 S p S n. Then D(n, p ) = [alr a,, ..., a,; a l , h l , b2, ..., bn-,, a,] is the digraph composed of a directed path ( a l , a z , ..., a,) of length p -1 and a directed path ( a l , h , , h 2 , ..., b,,-,, a,) of length np + 1, where a, # h,, for all i , j .

Griinbaum [4] and Thomassen [S, 91 have studied the problem of the existence of D(n, 2) in a tournament. Griinbaum proved that every tournament T of order n 2 3 contains D(n, 2) unless T is isomorphic to T: or TT (see Fig. 1). Thomassen proved that the minimum number of copies of D(n, 2) in a strong tournament is at least n -5 , and at least cn for some constant c > 1.