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.
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.
Accepté le :
Publié le :
@article{CRMATH_2005__341_8_465_0,
author = {Culus, Jean-Fran\c{c}ois and Jouve, Bertrand},
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},
url = {http://www.numdam.org/articles/10.1016/j.crma.2005.09.017/}
}
TY - JOUR AU - Culus, Jean-François AU - Jouve, Bertrand TI - Tournois sans intervalle acyclique JO - Comptes Rendus. Mathématique PY - 2005 SP - 465 EP - 468 VL - 341 IS - 8 PB - Elsevier UR - http://www.numdam.org/articles/10.1016/j.crma.2005.09.017/ DO - 10.1016/j.crma.2005.09.017 LA - fr ID - CRMATH_2005__341_8_465_0 ER -
%0 Journal Article %A Culus, Jean-François %A Jouve, Bertrand %T Tournois sans intervalle acyclique %J Comptes Rendus. Mathématique %D 2005 %P 465-468 %V 341 %N 8 %I Elsevier %U http://www.numdam.org/articles/10.1016/j.crma.2005.09.017/ %R 10.1016/j.crma.2005.09.017 %G fr %F CRMATH_2005__341_8_465_0
Culus, Jean-François; Jouve, Bertrand. Tournois sans intervalle acyclique. Comptes Rendus. Mathématique, Tome 341 (2005) no. 8, pp. 465-468. doi : 10.1016/j.crma.2005.09.017. http://www.numdam.org/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
Cité par Sources :
