Morphologie des tournois (−1)-critiques

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 sommet x d'un tournoi indécomposable T est critique si le tournoi T−x est décomposable. En 1993, J.H. Schmerl et W.T. Trotter ont caractérisé les tournois dont tous les sommets sont critiques, appelés tournois critiques. Ces tournois ont un cardinal impair ⩾5. Pour chaque entier impair m⩾5, il existe trois tournois critiques de cardinal m. Dans cet article, nous caractérisons les tournois qui admettent un unique sommet non critique, que nous appelons tournois (−1)-critiques. Ces tournois ont un cardinal impair ⩾7. Pour chaque entier impair m⩾7, il existe 3m−15 tournois (−1)-critiques de cardinal m. Notre travail prolonge une étude récente sur l'indécomposabilité et les sommets critiques faite par Y. Boudabbous et P. Ille. Pour citer cet article : H. Belkhechine et al., C. R. Acad. Sci. Paris, Ser. I 345 (2007).

Given a tournament T=(V,A), a subset X of V is an interval of T provided that for any 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. A vertex x of an indecomposable tournament is critical if T−x is decomposable. In 1993, J.H. Schmerl and W.T. Trotter characterized the tournaments, all the vertices of which are critical, called critical tournaments. The cardinality of these tournaments is odd. Given an odd integer m⩾5, there exist three critical tournaments of cardinality m. In this article, we characterize the tournaments which admit a single non critical vertex, that we call (−1)-critical tournaments. The cardinality of these tournaments is odd. Given an odd integer m⩾7, there exist 3m−15 (−1)-critical tournaments of cardinality m. Our work extends a recent study of indecomposability and critical vertices made by Y. Boudabbous and P. Ille. To cite this article: H. Belkhechine et al., C. R. Acad. Sci. Paris, Ser. I 345 (2007).