Realizing small tournaments through few permutations

Every tournament on 7 vertices is the majority relation of a 3-permutation profile, and there exist tournaments on 8 vertices that do not have this property. Furthermore every tournament on 8 or 9 vertices is the majority relation of a 5-permutation profile.

Saved in:
Bibliographic Details
Main Authors: Eggermont Christian
Hurkens Cor
Woeginger Gerhard J.
Format: Article
Published: 2013
Series:Acta cybernetica 21 No. 2
Kulcsszavak:Számítástechnika, Kibernetika
Subjects:
doi:10.14232/actacyb.21.2.2013.4

Online Access:http://acta.bibl.u-szeged.hu/32898
Description
Summary:Every tournament on 7 vertices is the majority relation of a 3-permutation profile, and there exist tournaments on 8 vertices that do not have this property. Furthermore every tournament on 8 or 9 vertices is the majority relation of a 5-permutation profile.
Physical Description:267-271
ISSN:0324-721X