Sous-tournois isomorphes à $ {W}_{5}$ dans un tournoi indécomposable

Belkhechine, Houmem; Boudabbous, Imed; Hzami, Kaouthar

doi:10.1016/j.crma.2012.03.012

Combinatoire

Sous-tournois isomorphes à

W_{5}

dans un tournoi indécomposable

Présenté par : le Comité de rédaction

Belkhechine, Houmem ¹ ; Boudabbous, Imed ² ; Hzami, Kaouthar ³

¹ Université de Carthage, Institut préparatoire aux études dʼingénieurs de Bizerte, Bizerte, Tunisie
² Université de Sfax, Institut préparatoire aux études dʼingénieurs de Sfax, Sfax, Tunisie
³ Université de Gabès, Institut supérieur dʼinformatique et de multimédia de Gabès, Gabès, Tunisie

Comptes Rendus. Mathématique, Tome 350 (2012) no. 7-8, pp. 333-337.

Résumé
Abstract

Considérons un tournoi $T = (S, A)$ . À chaque partie X de S est associé le sous-tournoi $T (X) = (X, A \cap (X \times X))$ de T induit par X. On dit que le tournoi T abrite un tournoi $T^{'}$ lorsque $T^{'}$ est isomorphe à un sous-tournoi de T. 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. En 2003, B.J. Latka a caractérisé la classe $T$ des tournois indécomposables nʼabritant pas un certain tournoi $W_{5}$ à 5 sommets. Dans cet article, nous nous intéressons, dans le cas dʼun tournoi indécomposable T, à lʼensemble $W_{5} (T)$ des sommets $x \in S$ pour lesquels il existe une partie X de S telle que $x \in X$ et $T (X)$ est isomorphe à $W_{5}$ . Nous montrons que pour un tournoi indécomposable T nʼappartenant pas à la classe $T$ , $| W_{5} (T) | ⩾ | S | - 2$ , et que $| W_{5} (T) | ⩾ | S | - 1$ lorsque $| S |$ est pair. À lʼaide dʼexemples, nous vérifions aussi que cet énoncé est optimal.

We consider a tournament $T = (V, A)$ . For each subset X of V is associated the subtournament $T (X) = (X, A \cap (X \times X))$ of T induced by X. We say that a tournament $T^{'}$ embeds into a tournament T when $T^{'}$ is isomorphic to a subtournament of T. A subset X of V is an interval of T provided that for $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 is indecomposable if all its intervals are trivial. In 2003, B.J. Latka characterized the class $T$ of the indecomposable tournaments into which a certain tournament $W_{5}$ on 5 vertices does not embed. In the case of an indecomposable tournament T, we study the set $W_{5} (T)$ of vertices $x \in V$ for which there exists a subset X of V such that $x \in X$ and $T (X)$ is isomorphic to $W_{5}$ . We prove the following: for any indecomposable tournament T, if $T \notin T$ , then $| W_{5} (T) | ⩾ | V | - 2$ and $| W_{5} (T) | ⩾ | V | - 1$ if $| V |$ is even. By giving examples, we also verify that this statement is optimal.

Reçu le : 2011-06-07
Accepté le : 2012-03-16
Publié le : 2012-03-30

DOI : 10.1016/j.crma.2012.03.012

Affiliations des auteurs :

Belkhechine, Houmem ¹ ; Boudabbous, Imed ² ; Hzami, Kaouthar ³

@article{CRMATH_2012__350_7-8_333_0,
     author = {Belkhechine, Houmem and Boudabbous, Imed and Hzami, Kaouthar},
     title = {Sous-tournois isomorphes \`a $ {W}_{5}$ dans un tournoi ind\'ecomposable},
     journal = {Comptes Rendus. Math\'ematique},
     pages = {333--337},
     publisher = {Elsevier},
     volume = {350},
     number = {7-8},
     year = {2012},
     doi = {10.1016/j.crma.2012.03.012},
     language = {fr},
     url = {http://www.numdam.org/articles/10.1016/j.crma.2012.03.012/}
}

TY  - JOUR
AU  - Belkhechine, Houmem
AU  - Boudabbous, Imed
AU  - Hzami, Kaouthar
TI  - Sous-tournois isomorphes à $ {W}_{5}$ dans un tournoi indécomposable
JO  - Comptes Rendus. Mathématique
PY  - 2012
SP  - 333
EP  - 337
VL  - 350
IS  - 7-8
PB  - Elsevier
UR  - http://www.numdam.org/articles/10.1016/j.crma.2012.03.012/
DO  - 10.1016/j.crma.2012.03.012
LA  - fr
ID  - CRMATH_2012__350_7-8_333_0
ER  -

%0 Journal Article
%A Belkhechine, Houmem
%A Boudabbous, Imed
%A Hzami, Kaouthar
%T Sous-tournois isomorphes à $ {W}_{5}$ dans un tournoi indécomposable
%J Comptes Rendus. Mathématique
%D 2012
%P 333-337
%V 350
%N 7-8
%I Elsevier
%U http://www.numdam.org/articles/10.1016/j.crma.2012.03.012/
%R 10.1016/j.crma.2012.03.012
%G fr
%F CRMATH_2012__350_7-8_333_0

Belkhechine, Houmem; Boudabbous, Imed; Hzami, Kaouthar. Sous-tournois isomorphes à $ {W}_{5}$ dans un tournoi indécomposable. Comptes Rendus. Mathématique, Tome 350 (2012) no. 7-8, pp. 333-337. doi : 10.1016/j.crma.2012.03.012. http://www.numdam.org/articles/10.1016/j.crma.2012.03.012/

Bibliographie
Cité par

[1] Belkhechine, H.; Boudabbous, I. Tournois indécomposables et leurs sous-tournois indécomposables à 5 sommets, C. R. Acad. Sci. Paris, Ser. I, Volume 343 (2006), pp. 685-688

[2] Benato, A.; Cameron, K. On an adjacency property of almost all tournaments, Discrete Math., Volume 306 (2006), pp. 2327-2335

[3] Cournier, A.; Ille, P. Minimal indecomposable graphs, Discrete Math., Volume 183 (1998), pp. 61-80

[4] Ebbinghauss, H.-D.; Flum, J. Finite Model Theory, Springer Monographs in Mathematics, 1999

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

[6] Erdös, P.; Fried, E.; Hajnal, A.; Milner, C. Some remarks on simple tournaments, Algebra Universalis, Volume 2 (1972), pp. 238-245

[7] Fagin, R. Probabilities on finite models, J. Symbolic Logic, Volume 41 (1976), pp. 50-58

[8] Fagin, R. Finite-model theory – a personal perspective, Theoret. Comput. Sci., Volume 116 (1993), pp. 3-31

[9] 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, Amsterdam, 1984, pp. 313-342

[10] Gnanvo, C.; Ille, P. La reconstruction des tournois sans diamants, Z. Math. Logik Grundlag. Math., Volume 38 (1992), pp. 283-291

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

[12] Latka, B.J. Structure theorem for tournaments omitting $N_{5}$ , J. Graph Theory, Volume 42 (2003), pp. 165-192

[13] Lopez, G.; Rozy, C. Reconstruction of binary relations from their restrictions of cardinality 2, 3, 4 and $(n - 1)$ , I, Z. Math. Logik Grundlag. Math., Volume 38 (1992), pp. 27-37

[14] Mueller, V.J.; Nesetril, J.; Pelant, J. Either tournaments or algebras ?, Discrete Math., Volume 11 (1975), pp. 37-66

[15] Sayar, M.Y. Partially critical tournaments and partially critical supports, Contrib. Discrete Math., Volume 6 (2011), pp. 52-76

[16] 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 :