Vol. 21, No. 3, 1967

Download this article
Download this article. For screen
For printing
Recent Issues
Vol. 329: 1
Vol. 328: 1  2
Vol. 327: 1  2
Vol. 326: 1  2
Vol. 325: 1  2
Vol. 324: 1  2
Vol. 323: 1  2
Vol. 322: 1  2
Online Archive
The Journal
About the journal
Ethics and policies
Peer-review process
Submission guidelines
Submission form
Editorial board
ISSN: 1945-5844 (e-only)
ISSN: 0030-8730 (print)
Special Issues
Author index
To appear
Other MSP journals
Generating oriented graphs by means of team comparisons

John W. Moon and Leo Moser

Vol. 21 (1967), No. 3, 531–535

Two teams A and B can be compared by matching each player in A against each player in B. We say that A > B if and only if the players of A collectively win more games against players of B than they lose. If there are n teams T1,T2,,Tn, then the outcomes of the matches between the various teams may be represented by an oriented graph Hn on n nodes in which an arc goes from the i-th node to the j-th node if and only if Tj > Tj. It is shown that any oriented graph can be generated in this way, and that the minimum number of players necessary to generate any oriented graph Hn is of the order of nzlog n.

Mathematical Subject Classification
Primary: 05.65
Received: 25 July 1966
Published: 1 June 1967
John W. Moon
Leo Moser