Comptes Rendus
Combinatoire
Sous-tournois isomorphes à W5 dans un tournoi indécomposable
Comptes Rendus. Mathématique, Volume 350 (2012) no. 7-8, pp. 333-337.

Considérons un tournoi T=(S,A). À chaque partie X de S est associé le sous-tournoi T(X)=(X,A(X×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,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. En 2003, B.J. Latka a caractérisé la classe T des tournois indécomposables nʼabritant pas un certain tournoi W5 à 5 sommets. Dans cet article, nous nous intéressons, dans le cas dʼun tournoi indécomposable T, à lʼensemble W5(T) des sommets xS pour lesquels il existe une partie X de S telle que xX et T(X) est isomorphe à W5. Nous montrons que pour un tournoi indécomposable T nʼappartenant pas à la classe T, |W5(T)||S|2, et que |W5(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(X×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,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 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 W5 on 5 vertices does not embed. In the case of an indecomposable tournament T, we study the set W5(T) of vertices xV for which there exists a subset X of V such that xX and T(X) is isomorphic to W5. We prove the following: for any indecomposable tournament T, if TT, then |W5(T)||V|2 and |W5(T)||V|1 if |V| is even. By giving examples, we also verify that this statement is optimal.

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

Houmem Belkhechine 1 ; Imed Boudabbous 2 ; Kaouthar Hzami 3

1 Université de Carthage, Institut préparatoire aux études dʼingénieurs de Bizerte, Bizerte, Tunisie
2 Université de Sfax, Institut préparatoire aux études dʼingénieurs de Sfax, Sfax, Tunisie
3 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/

[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 N5, 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 (n1), 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