The indecomposable tournaments <i>T</i> with $ |{W}_{5}(T)|=|T|-2$

Belkhechine, Houmem; Boudabbous, Imed; Hzami, Kaouthar

doi:10.1016/j.crma.2013.07.021

Combinatorics

The indecomposable tournaments T with

| W_{5} (T) | = | T | - 2

[Les tournois indécomposables T tels que

| W_{5} (T) | = | T | - 2

]

Présenté par : the Editorial Board

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

¹ Carthage University, Bizerte Preparatory Engineering Institute, Tunisia
² Sfax University, Sfax Preparatory Engineering Institute, Tunisia
³ Gabes University, Higher Institute of Computer Sciences and Multimedia of Gabes, Tunisia

Comptes Rendus. Mathématique, Tome 351 (2013) no. 13-14, pp. 501-504.

Résumé
Abstract

Considérons un tournoi $T = (V, A)$ . Pour $X \subseteq V$ , le sous-tournoi de T induit par X est $T [X] = (X, A \cap (X \times X))$ . Un intervalle de T est une partie X de V telle que, pour tous $a, b \in X$ et $x \in V ∖ X$ , $(a, x) \in A$ si et seulement si $(b, x) \in A$ . Les intervalles triviaux de T sont ∅, ${x} (x \in V)$ et V. Un tournoi est indécomposable si tous ses intervalles sont triviaux. Pour $n ⩾ 2$ , $W_{2 n + 1}$ est lʼunique tournoi indécomposable défini sur ${0, \dots, 2 n}$ tel que $W_{2 n + 1} [{0, \dots, 2 n - 1}]$ est lʼordre total usuel. Étant donné un tournoi indécomposable T, $W_{5} (T)$ désigne lʼensemble des sommets $v \in V$ pour lesquels il existe une partie W de V telle que $v \in W$ et $T [W]$ est isomorphe à $W_{5}$ . Latka [6] a caractérisé les tournois indécomposables T tels que $W_{5} (T) = \emptyset$ . Les auteurs [1] ont prouvé que, si $W_{5} (T) \neq \emptyset$ , alors $| W_{5} (T) | ⩾ | V | - 2$ . Dans cette note, nous caractérisons les tournois indécomposables T tels que $| W_{5} (T) | = | V | - 2$ .

We consider a tournament $T = (V, A)$ . For $X \subseteq V$ , the subtournament of T induced by X is $T [X] = (X, A \cap (X \times X))$ . An interval of T is a subset X of V such that, for $a, b \in X$ and $x \in V ∖ X$ , $(a, x) \in A$ if and only if $(b, x) \in A$ . The trivial intervals of T are ∅, ${x} (x \in V)$ and V. A tournament is indecomposable if all its intervals are trivial. For $n ⩾ 2$ , $W_{2 n + 1}$ denotes the unique indecomposable tournament defined on ${0, \dots, 2 n}$ such that $W_{2 n + 1} [{0, \dots, 2 n - 1}]$ is the usual total order. Given an indecomposable tournament T, $W_{5} (T)$ denotes the set of $v \in V$ such that there is $W \subseteq V$ satisfying $v \in W$ and $T [W]$ is isomorphic to $W_{5}$ . Latka [6] characterized the indecomposable tournaments T such that $W_{5} (T) = \emptyset$ . The authors [1] proved that if $W_{5} (T) \neq \emptyset$ , then $| W_{5} (T) | ⩾ | V | - 2$ . In this note, we characterize the indecomposable tournaments T such that $| W_{5} (T) | = | V | - 2$ .

Reçu le : 2013-06-30
Accepté le : 2013-07-31
Publié le : 2013-07-01

DOI : 10.1016/j.crma.2013.07.021

Affiliations des auteurs :

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

@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://archive.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://archive.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://archive.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, Tome 351 (2013) no. 13-14, pp. 501-504. doi : 10.1016/j.crma.2013.07.021. http://archive.numdam.org/articles/10.1016/j.crma.2013.07.021/

Bibliographie
Cité par

[1] Belkhechine, H.; Boudabbous, I.; Hzami, K. Sous-tournois isomorphes à $W_{5}$ 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 $| W_{5} (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 $N_{5}$ , 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

Cité par Sources :