Hostname: page-component-78c5997874-m6dg7 Total loading time: 0 Render date: 2024-11-03T01:10:50.391Z Has data issue: false hasContentIssue false

The Maximum Number of Strongly Connected Subtournaments*

Published online by Cambridge University Press:  20 November 2018

Lowell W. Beineke
Affiliation:
The University of Michigan
Frank Harary
Affiliation:
The University of Michigan
Rights & Permissions [Opens in a new window]

Extract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

In the ranking of a collection of p objects by the method of paired comparisons, a measure of consistency is provided by the relative number of transitive (or consistent) triples and cyclic (or inconsistent) triples. This point of view was introduced by Kendall and Babington Smith [4]. They found a formula for the maximum number of cyclic triples, thereby determining the greatest inconsistency possible. The purpose of this note is to extend the result to obtain the maximum number of "strongly connected" collections of n objects among the given p objects.

Type
Research Article
Copyright
Copyright © Canadian Mathematical Society 1965

Footnotes

*

The preparation of this article was supported by the National Science Foundation under Grant G-17771.

References

1. Berge, C., Théorie des graphes et ses applications, Paris, Dunod, 1958.Google Scholar
2. Harary, F. and Moser, L., The theory of round robin tournaments, Amer. Math. Monthly, to appear.Google Scholar
3. Harary, F., Norman, R., and Cartwright, D., Structural models: an introduction to the theory of directed graphs, New York, 1965.Google Scholar
4. Kendall, M. G. and Babington Smith, B., On the method of paired comparisons, Biometrika, 31 (1940) 324-345.Google Scholar