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

Belkhechine, Houmem; Boudabbous, Imed

doi:10.1016/j.crma.2006.10.029

Logique/Combinatoire

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

Présenté par : Jean-Yves Girard

Belkhechine, Houmem ¹ ; Boudabbous, Imed ²

¹ Université du 7 novembre à Carthage, institut supérieur des sciences appliquées et de technologie de Mateur, route de Tabarka, 7030 Mateur, Tunisie
² Université de Sfax, institut supérieur de biotechnologies, route de la Sokra Km 4, BP 38, 3080 Sfax, Tunisie

Comptes Rendus. Mathématique, Tome 343 (2006) no. 11-12, pp. 685-688.

Résumé
Abstract

Étant donné un tournoi $T = (S, A)$ , une partie X de S est un intervalle de T lorsque pour tous $a, b \in X$ et $x \in S - X$ , $(a, x) \in A$ si et seulement si $(b, x) \in A$ . Par exemple, ∅, ${x} (x \in 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 $T_{5}$ , $U_{5}$ et $V_{5}$ . 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 à $T_{5}$ et nous montrons que si un tournoi indécomposable, n'appartenant pas à la classe $T$ , abrite $T_{5}$ , alors il abrite $V_{5}$ et $U_{5}$ .

Given a tournament $T = (V, A)$ , a subset X of V is an interval of T provided that for every $a, b \in X$ and $x \in V - X$ , $(a, x) \in A$ if and only if $(b, x) \in A$ . For example, ∅, ${x} (x \in 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 $T_{5}$ , $U_{5}$ and $V_{5}$ . 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 $T_{5}$ and we prove that, if $T_{5}$ embeds in an indecomposable tournament T, not belonging to the class $T$ , then each of $V_{5}$ and $U_{5}$ embeds in T.

Reçu le : 2006-10-18
Accepté le : 2006-10-27
Publié le : 2006-12-01

DOI : 10.1016/j.crma.2006.10.029

Affiliations des auteurs :

Belkhechine, Houmem ¹ ; Boudabbous, Imed ²

@article{CRMATH_2006__343_11-12_685_0,
     author = {Belkhechine, Houmem and Boudabbous, Imed},
     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},
     url = {http://www.numdam.org/articles/10.1016/j.crma.2006.10.029/}
}

TY  - JOUR
AU  - Belkhechine, Houmem
AU  - Boudabbous, Imed
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
UR  - http://www.numdam.org/articles/10.1016/j.crma.2006.10.029/
DO  - 10.1016/j.crma.2006.10.029
LA  - fr
ID  - CRMATH_2006__343_11-12_685_0
ER  -

%0 Journal Article
%A Belkhechine, Houmem
%A Boudabbous, Imed
%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
%U http://www.numdam.org/articles/10.1016/j.crma.2006.10.029/
%R 10.1016/j.crma.2006.10.029
%G fr
%F CRMATH_2006__343_11-12_685_0

Belkhechine, Houmem; Boudabbous, Imed. Tournois indécomposables et leurs sous-tournois indécomposables à 5 sommets. Comptes Rendus. Mathématique, Tome 343 (2006) no. 11-12, pp. 685-688. doi : 10.1016/j.crma.2006.10.029. http://www.numdam.org/articles/10.1016/j.crma.2006.10.029/

Bibliographie
Cité par

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

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

[3] Fraïssé, R. 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

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

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

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

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

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

Cité par Sources :