Cycles in k-strong tournaments

Myron Goldberg and John W. Moon

Vol. 40 (1972), No. 1, 89–96

DOI: 10.2140/pjm.1972.40.89

Abstract

A tournament T_n with n nodes is k-strong if k is the largest integer such that for every partition of the nodes of T_n into two nonempty subsets A and B there are at least k arcs that go from nodes of A to nodes of B and conversely. The main result is that every k-strong tournament has at least k different spanning cycles.

Mathematical Subject Classification 2000

Primary: 05C20

Milestones

Received: 11 December 1970

Revised: 27 April 1971

Published: 1 January 1972