Étant donné un tournoi , une partie X de S est un intervalle de T lorsque pour tous et , si et seulement si . Par exemple, ∅, 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 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 , 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 , il existe tournois -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.
Given a tournament , a subset X of V is an interval of T provided that for any and , if and only if . For example, ∅, 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 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 , 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 -critical tournaments. The cardinality of these tournaments is odd. Given an odd integer , there exist -critical tournaments of cardinality m. Our work extends a recent study of indecomposability and critical vertices made by Y. Boudabbous and P. Ille.
Accepté le :
Publié le :
@article{CRMATH_2007__345_12_663_0,
author = {Belkhechine, Houmem and Boudabbous, Imed and Dammak, Jamel},
title = {Morphologie des tournois (\ensuremath{-}1)-critiques},
journal = {Comptes Rendus. Math\'ematique},
pages = {663--666},
publisher = {Elsevier},
volume = {345},
number = {12},
year = {2007},
doi = {10.1016/j.crma.2007.11.006},
language = {fr},
url = {http://www.numdam.org/articles/10.1016/j.crma.2007.11.006/}
}
TY - JOUR AU - Belkhechine, Houmem AU - Boudabbous, Imed AU - Dammak, Jamel TI - Morphologie des tournois (−1)-critiques JO - Comptes Rendus. Mathématique PY - 2007 SP - 663 EP - 666 VL - 345 IS - 12 PB - Elsevier UR - http://www.numdam.org/articles/10.1016/j.crma.2007.11.006/ DO - 10.1016/j.crma.2007.11.006 LA - fr ID - CRMATH_2007__345_12_663_0 ER -
%0 Journal Article %A Belkhechine, Houmem %A Boudabbous, Imed %A Dammak, Jamel %T Morphologie des tournois (−1)-critiques %J Comptes Rendus. Mathématique %D 2007 %P 663-666 %V 345 %N 12 %I Elsevier %U http://www.numdam.org/articles/10.1016/j.crma.2007.11.006/ %R 10.1016/j.crma.2007.11.006 %G fr %F CRMATH_2007__345_12_663_0
Belkhechine, Houmem; Boudabbous, Imed; Dammak, Jamel. Morphologie des tournois (−1)-critiques. Comptes Rendus. Mathématique, Tome 345 (2007) no. 12, pp. 663-666. doi : 10.1016/j.crma.2007.11.006. http://www.numdam.org/articles/10.1016/j.crma.2007.11.006/
[1] Critical and infinite directed graphs, Discrete Math., Volume 307 (2007), pp. 2415-2428
[2] Y. Boudabbous, P. Ille, Indecomposability graph and critical vertices of an indecomposable graph, soumis à Discrete Math
[3] Primitivity is hereditary for 2-structures, Theoret. Comput. Sci., Volume 3 (1990) no. 70, pp. 343-358
[4] L'intervalle en théorie des relations, ses généralisations, filtre intervallaire et clôture d'une relation (Pouzet, M.; Richard, D., eds.), Orders, Description and Roles, North-Holland, 1984, pp. 313-342
[5] Indecomposable graphs, Discrete Math., Volume 173 (1997), pp. 71-78
[6] Recognition problem in reconstruction for decomposable relations (Sands, B.; Sauer, N.; Woodrow, R., eds.), Finite and Infinite Combinatorics in Sets and Logic, Kluwer Academic Publishers, 1993, pp. 189-198
[7] Critically indecomposable partially ordered sets, graphs, tournaments and other binary relational structures, Discrete Math., Volume 113 (1993), pp. 191-205
Cité par Sources :
