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

Houmem Belkhechine; Imed Boudabbous; Kaouthar Hzami

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

Houmem Belkhechine ¹ ; Imed Boudabbous ² ; Kaouthar Hzami ³

¹ 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, Volume 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 :

Houmem Belkhechine ¹ ; Imed Boudabbous ² ; Kaouthar Hzami ³

¹ 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

@article{CRMATH_2012__350_7-8_333_0,
     author = {Houmem Belkhechine and Imed Boudabbous and Kaouthar Hzami},
     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},
}

TY  - JOUR
AU  - Houmem Belkhechine
AU  - Imed Boudabbous
AU  - Kaouthar Hzami
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
DO  - 10.1016/j.crma.2012.03.012
LA  - fr
ID  - CRMATH_2012__350_7-8_333_0
ER  -

%0 Journal Article
%A Houmem Belkhechine
%A Imed Boudabbous
%A Kaouthar Hzami
%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
%R 10.1016/j.crma.2012.03.012
%G fr
%F CRMATH_2012__350_7-8_333_0

Houmem Belkhechine; Imed Boudabbous; Kaouthar Hzami. Sous-tournois isomorphes à $ {W}_{5}$ dans un tournoi indécomposable. Comptes Rendus. Mathématique, Volume 350 (2012) no. 7-8, pp. 333-337. doi : 10.1016/j.crma.2012.03.012. https://comptes-rendus.academie-sciences.fr/mathematique/articles/10.1016/j.crma.2012.03.012/

Bibliographie
Cité par

[1] H. Belkhechine; I. Boudabbous 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] A. Benato; K. Cameron On an adjacency property of almost all tournaments, Discrete Math., Volume 306 (2006), pp. 2327-2335

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

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

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

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

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

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

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

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

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

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

[13] G. Lopez; C. Rozy 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] V.J. Mueller; J. Nesetril; J. Pelant Either tournaments or algebras ?, Discrete Math., Volume 11 (1975), pp. 37-66

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

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