On 5‐Cycles and 6‐Cycles in Regular n‐Tournaments |
| |
| Authors: | S. V. Savchenko |
| |
| Affiliation: | L.D. LANDAU INSTITUTE FOR THEORETICAL PHYSICS, RUSSIAN ACADEMY OF SCIENCES, MOSCOW, RUSSIADedicated to Richard Brualdi on the occasion of his 75th birthday. |
| |
| Abstract: | ![]()
Let T be a tournament of order n and  be the number of cycles of length m in T. For  and odd n, the maximum of  is achieved for any regular tournament of order n (M. G. Kendall and B. Babington Smith, 1940), and in the case  it is attained only for the unique regular locally transitive tournament RLTn of order n (U. Colombo, 1964). A lower bound was also obtained for  in the class  of regular tournaments of order n (A. Kotzig, 1968). This bound is attained if and only if T is doubly regular (when  ) or nearly doubly regular (when  ) (B. Alspach and C. Tabib, 1982). In the present article, we show that for any regular tournament T of order n, the equality  holds. This allows us to reduce the case  to the case  In turn, the pure spectral expression for  obtained in the class  implies that for a regular tournament T of order  the inequality  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 c6(RLTn) and conjecture that this value coincides with the minimum number of 6‐cycles in the class  for each odd  |
| |
| Keywords: | tournament transitive tournament locally transitive tournament regular tournament doubly regular tournament quadratic residue tournament 05C20 05C38 05C50 |
|
|
