Comptes Rendus
Logique/Combinatoire
Tournois indécomposables et leurs sous-tournois indécomposables à 5 sommets
Comptes Rendus. Mathématique, Volume 343 (2006) no. 11-12, pp. 685-688.

Étant donné un tournoi T=(S,A), une partie X de S est un intervalle de T lorsque pour tous a,bX et xSX, (a,x)A si et seulement si (b,x)A. Par exemple, ∅, {x}(xS) 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.

Given a tournament T=(V,A), a subset X of V is an interval of T provided that for every a,bX and xVX, (a,x)A if and only if (b,x)A. For example, ∅, {x}(xV) 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.

Reçu le :
Accepté le :
Publié le :
DOI : 10.1016/j.crma.2006.10.029

Houmem Belkhechine 1 ; Imed Boudabbous 2

1 Université du 7 novembre à Carthage, institut supérieur des sciences appliquées et de technologie de Mateur, route de Tabarka, 7030 Mateur, Tunisie
2 Université de Sfax, institut supérieur de biotechnologies, route de la Sokra Km 4, BP 38, 3080 Sfax, Tunisie
@article{CRMATH_2006__343_11-12_685_0,
     author = {Houmem Belkhechine and Imed Boudabbous},
     title = {Tournois ind\'ecomposables et leurs sous-tournois ind\'ecomposables \`a 5 sommets},
     journal = {Comptes Rendus. Math\'ematique},
     pages = {685--688},
     publisher = {Elsevier},
     volume = {343},
     number = {11-12},
     year = {2006},
     doi = {10.1016/j.crma.2006.10.029},
     language = {fr},
}
TY  - JOUR
AU  - Houmem Belkhechine
AU  - Imed Boudabbous
TI  - Tournois indécomposables et leurs sous-tournois indécomposables à 5 sommets
JO  - Comptes Rendus. Mathématique
PY  - 2006
SP  - 685
EP  - 688
VL  - 343
IS  - 11-12
PB  - Elsevier
DO  - 10.1016/j.crma.2006.10.029
LA  - fr
ID  - CRMATH_2006__343_11-12_685_0
ER  - 
%0 Journal Article
%A Houmem Belkhechine
%A Imed Boudabbous
%T Tournois indécomposables et leurs sous-tournois indécomposables à 5 sommets
%J Comptes Rendus. Mathématique
%D 2006
%P 685-688
%V 343
%N 11-12
%I Elsevier
%R 10.1016/j.crma.2006.10.029
%G fr
%F CRMATH_2006__343_11-12_685_0
Houmem Belkhechine; Imed Boudabbous. Tournois indécomposables et leurs sous-tournois indécomposables à 5 sommets. Comptes Rendus. Mathématique, Volume 343 (2006) no. 11-12, pp. 685-688. doi : 10.1016/j.crma.2006.10.029. https://comptes-rendus.academie-sciences.fr/mathematique/articles/10.1016/j.crma.2006.10.029/

[1] Y. Boudabbous; J. Dammak; P. Ille Indecomposability and duality of tournaments, Discrete Math., Volume 223 (2000), pp. 55-82

[2] A. Ehrenfeucht; G. Rozenberg Primitivity is hereditary for 2-structures, Theoret. Comput. Sci., Volume 3 (1990) no. 70, pp. 343-358

[3] R. Fraïssé L'intervalle en théorie des relations, ses généralisations, filtre intervallaire et clôture d'une relation (M. Pouzet; D. Richard, eds.), Orders, Description and Roles, North-Holland, 1984, pp. 313-342

[4] T. Gallai Transitiv orientierbare Graphen, Acta. Math. Acad. Sci. Hungar., Volume 18 (1967), pp. 25-66

[5] P. Ille Indecomposable graphs, Discrete Math., Volume 173 (1997), pp. 71-78

[6] W.M. Kantor Automorphism groups of designs, Math. Z., Volume 109 (1969), pp. 246-252

[7] B.J. Latka A structure theorem of tournaments omitting N5, J. Graph Theory, Volume 42 (2003), pp. 165-192

[8] J.H. Schmerl; W.T. Trotter Critically indecomposable partially ordered sets, graphs, tournaments and other binary relational structures, Discrete Math., Volume 113 (1993), pp. 191-205

Cité par Sources :

Commentaires - Politique