Premium
On 5‐Cycles and 6‐Cycles in Regular n‐Tournaments
Author(s) -
Savchenko S. V.
Publication year - 2016
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.21914
Subject(s) - tournament , mathematics , combinatorics , order (exchange) , conjecture , transitive relation , upper and lower bounds , value (mathematics) , class (philosophy) , discrete mathematics , statistics , mathematical analysis , finance , artificial intelligence , computer science , economics
Let T be a tournament of order n andc m ( T )be the number of cycles of length m in T . For m = 3 and odd n , the maximum ofc m ( T )is achieved for any regular tournament of order n (M. G. Kendall and B. Babington Smith, 1940), and in the case m = 4 , it is attained only for the unique regular locally transitive tournament RLT n of order n (U. Colombo, 1964). A lower bound was also obtained forc 4 ( T )in the class R n of regular tournaments of order n (A. Kotzig, 1968). This bound is attained if and only if T is doubly regular (when n ≡ 3mod4 ) or nearly doubly regular (when n ≡ 1mod4 ) (B. Alspach and C. Tabib, 1982). In the present article, we show that for any regular tournament T of order n , the equality 2 c 4 ( T ) + c 5 ( T ) = n ( n − 1 ) ( n + 1 ) ( n − 3 ) ( n + 3 ) / 160 holds. This allows us to reduce the case m = 5 to the case m = 4 . In turn, the pure spectral expression forc 6 ( T )obtained in the class R n implies that for a regular tournament T of order n ≥ 7 , the inequalityc 6 ( T ) ≤ n ( n − 1 ) ( n + 1 ) ( n − 3 ) ( n 2 − 6 n + 3 ) / 384 holds, with equality if and only if T is doubly regular or T is the unique regular tournament of order 7 that is neither doubly regular nor locally transitive. We also determine the value of c 6 ( RLT n ) and conjecture that this value coincides with the minimum number of 6‐cycles in the class R n for each odd n ≥ 7 .