[Tournaments without acyclic interval]
An interval X of a tournament T is a vertex subset of T such that any vertex not in X either dominates or is dominated by all of the vertices in X. We caracterize the tournaments such that the only non empty acyclic intervals are the singletons and which are critical for that property, that is whenever a vertex is removed at least one acyclic interval with more than 2 vertices is created. These tournaments are exactly those which are the composition of any tournament with circulant tournaments. That work on acyclic intervals was motivated by the study of tournaments for which no median order forced itself naturally.
Un intervalle X d'un tournoi T est un ensemble de sommets de T tel que tout sommet extérieur à X domine ou est dominé par tous les sommets de X. Nous caractérisons les tournois dont tous les intervalles acycliques non vides sont des singletons et qui sont critiques pour cette propriété, c'est-à-dire que la suppression d'un sommet quelconque du tournoi donne naissance à au moins un intervalle acyclique de plus de 2 sommets. Ces tournois sont exactement ceux construits comme la composition d'un tournoi quelconque avec des tournois circulants. Ce travail sur les intervalles acycliques a été motivé par la recherche de structures ordonnées dans des tournois pour lesquels aucun ordre médian ne s'impose naturellement.
Accepted:
Published online:
Jean-François Culus 1; Bertrand Jouve 1
@article{CRMATH_2005__341_8_465_0,
author = {Jean-Fran\c{c}ois Culus and Bertrand Jouve},
title = {Tournois sans intervalle acyclique},
journal = {Comptes Rendus. Math\'ematique},
pages = {465--468},
publisher = {Elsevier},
volume = {341},
number = {8},
year = {2005},
doi = {10.1016/j.crma.2005.09.017},
language = {fr},
}
Jean-François Culus; Bertrand Jouve. Tournois sans intervalle acyclique. Comptes Rendus. Mathématique, Volume 341 (2005) no. 8, pp. 465-468. doi : 10.1016/j.crma.2005.09.017. https://comptes-rendus.academie-sciences.fr/mathematique/articles/10.1016/j.crma.2005.09.017/
[1] Indecomposability and duality of tournaments, Discrete Math., Volume 223 (2000), pp. 55-82
[2] Indecomposable graphs, Discrete Math., Volume 173 (1997), pp. 71-78
[3] B. Jouve, Transitive convex subsets in large tournaments, Electronic Notes in Discrete Math., in press
[4] Tournament Solutions and Majority Voting, Springer, Berlin, 1997
[5] Linear-time modular decomposition of directed graphs, Discrete Appl. Math., Volume 145 (2005), pp. 189-209
[6] Vertex critical r-dichromatic tournaments, Discrete Math., Volume 49 (1984), pp. 83-87
[7] Critically indecomposable partially ordered sets, graphs, tournaments and other binary relational structures, Discrete Math., Volume 113 (1993), pp. 191-205
Cited by Sources:
Comments - Policy