Combinatorics
The indecomposable tournaments T with |W5(T)|=|T|2
Comptes Rendus. Mathématique, Volume 351 (2013) no. 13-14, pp. 501-504.

We consider a tournament T=(V,A). For XV, the subtournament of T induced by X is T[X]=(X,A(X×X)). An interval of T is a subset X of V such that, for a,bX and xVX, (a,x)A if and only if (b,x)A. The trivial intervals of T are ∅, {x}(xV) and V. A tournament is indecomposable if all its intervals are trivial. For n2, W2n+1 denotes the unique indecomposable tournament defined on {0,,2n} such that W2n+1[{0,,2n1}] is the usual total order. Given an indecomposable tournament T, W5(T) denotes the set of vV such that there is WV satisfying vW and T[W] is isomorphic to W5. Latka [6] characterized the indecomposable tournaments T such that W5(T)=. The authors [1] proved that if W5(T), then |W5(T)||V|2. In this note, we characterize the indecomposable tournaments T such that |W5(T)|=|V|2.

Considérons un tournoi T=(V,A). Pour XV, le sous-tournoi de T induit par X est T[X]=(X,A(X×X)). Un intervalle de T est une partie X de V telle que, pour tous a,bX et xVX, (a,x)A si et seulement si (b,x)A. Les intervalles triviaux de T sont ∅, {x}(xV) et V. Un tournoi est indécomposable si tous ses intervalles sont triviaux. Pour n2, W2n+1 est lʼunique tournoi indécomposable défini sur {0,,2n} tel que W2n+1[{0,,2n1}] est lʼordre total usuel. Étant donné un tournoi indécomposable T, W5(T) désigne lʼensemble des sommets vV pour lesquels il existe une partie W de V telle que vW et T[W] est isomorphe à W5. Latka [6] a caractérisé les tournois indécomposables T tels que W5(T)=. Les auteurs [1] ont prouvé que, si W5(T), alors |W5(T)||V|2. Dans cette note, nous caractérisons les tournois indécomposables T tels que |W5(T)|=|V|2.

Received:
Accepted:
Published online:
DOI: 10.1016/j.crma.2013.07.021
Belkhechine, Houmem 1; Boudabbous, Imed 2; Hzami, Kaouthar 3

1 Carthage University, Bizerte Preparatory Engineering Institute, Tunisia
2 Sfax University, Sfax Preparatory Engineering Institute, Tunisia
3 Gabes University, Higher Institute of Computer Sciences and Multimedia of Gabes, Tunisia
@article{CRMATH_2013__351_13-14_501_0,
     author = {Belkhechine, Houmem and Boudabbous, Imed and Hzami, Kaouthar},
     title = {The indecomposable tournaments {\protect\emph{T}} with $ |{W}_{5}(T)|=|T|-2$},
     journal = {Comptes Rendus. Math\'ematique},
     pages = {501--504},
     publisher = {Elsevier},
     volume = {351},
     number = {13-14},
     year = {2013},
     doi = {10.1016/j.crma.2013.07.021},
     language = {en},
     url = {http://www.numdam.org/articles/10.1016/j.crma.2013.07.021/}
}
TY  - JOUR
AU  - Belkhechine, Houmem
AU  - Boudabbous, Imed
AU  - Hzami, Kaouthar
TI  - The indecomposable tournaments T with $ |{W}_{5}(T)|=|T|-2$
JO  - Comptes Rendus. Mathématique
PY  - 2013
SP  - 501
EP  - 504
VL  - 351
IS  - 13-14
PB  - Elsevier
UR  - http://www.numdam.org/articles/10.1016/j.crma.2013.07.021/
DO  - 10.1016/j.crma.2013.07.021
LA  - en
ID  - CRMATH_2013__351_13-14_501_0
ER  - 
%0 Journal Article
%A Belkhechine, Houmem
%A Boudabbous, Imed
%A Hzami, Kaouthar
%T The indecomposable tournaments T with $ |{W}_{5}(T)|=|T|-2$
%J Comptes Rendus. Mathématique
%D 2013
%P 501-504
%V 351
%N 13-14
%I Elsevier
%U http://www.numdam.org/articles/10.1016/j.crma.2013.07.021/
%R 10.1016/j.crma.2013.07.021
%G en
%F CRMATH_2013__351_13-14_501_0
Belkhechine, Houmem; Boudabbous, Imed; Hzami, Kaouthar. The indecomposable tournaments T with $ |{W}_{5}(T)|=|T|-2$. Comptes Rendus. Mathématique, Volume 351 (2013) no. 13-14, pp. 501-504. doi : 10.1016/j.crma.2013.07.021. http://www.numdam.org/articles/10.1016/j.crma.2013.07.021/

[1] Belkhechine, H.; Boudabbous, I.; Hzami, K. Sous-tournois isomorphes à W5 dans un tournoi indécomposable, C. R. Acad. Sci. Paris, Ser. I, Volume 350 (2012), pp. 333-337

[2] Belkhechine, H.; Boudabbous, I.; Hzami, K. The indecomposable tournaments T with |W5(T)|=|T|2, 2013 | arXiv

[3] Breiner, A.; Deogun, J.; Ille, P. Partially critical indecomposable graphs, Contrib. Discrete Math., Volume 3 (2008), pp. 40-59

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

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

[6] Latka, B.J. Structure theorem for tournaments omitting N5, J. Graph Theory, Volume 42 (2003), pp. 165-192

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

[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

Cited by Sources: