Tournois indécomposables et leurs sous-tournois indécomposables à 5 sommets

RésuméÉtant donné un tournoi T=(S,A), une partie X de S est un intervalle de T lorsque pour tous a,b∈X et x∈S−X, (a,x)∈A si et seulement si (b,x)∈A. Par exemple, ∅, {x}(x∈S) et S sont des intervalles de T, appelés intervalles triviaux. Un tournoi dont tous les intervalles sont triviaux, est indécomposable ; sinon, il est décomposable. À un isomorphisme près, les tournois indécomposables à 5 sommets sont au nombre de trois. Nous les notons T5, U5 et V5. On dit qu'un tournoi T abrite un tournoi T′ si T′ est isomorphe à un sous-tournoi de T. Cette Note consiste en une étude morphologique des tournois indécomposables, que nous présentons suivant les tournois indécomposales à 5 sommets qu'ils abritent. Nous caractérisons la classe T des tournois indécomposables dont tous les sous-tournois indécomposales à 5 sommets sont isomorphes à T5 et nous montrons que si un tournoi indécomposable, n'appartenant pas à la classe T, abrite T5, alors il abrite V5 et U5. Pour citer cet article : H. Belkhechine, I. Boudabbous, C. R. Acad. Sci. Paris, Ser. I 343 (2006).

Given a tournament T=(V,A), a subset X of V is an interval of T provided that for every a,b∈X and x∈V−X, (a,x)∈A if and only if (b,x)∈A. For example, ∅, {x}(x∈V) and V are intervals of T, called trivial intervals. A tournament, all the intervals of which are trivial, is indecomposable; otherwise, it is decomposable. Up to an isomorphism, there are exactly three indecomposable tournaments with 5 vertices denoted by T5, U5 and V5. We say that a tournament T embeds in a tournament T′ when T is isomorphic to a subtournament of T′. This Note consists of a morphologic study of indecomposable tournaments, which we present according to the indecomposable subtournaments with 5 vertices embedding in. We characterize the class T of indecomposable tournaments, all indecomposable subtournaments with 5 vertices of which are isomorphic to T5 and we prove that, if T5 embeds in an indecomposable tournament T, not belonging to the class T, then each of V5 and U5 embeds in T. To cite this article: H. Belkhechine, I. Boudabbous, C. R. Acad. Sci. Paris, Ser. I 343 (2006).