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

Houmem Belkhechine; Imed Boudabbous; Kaouthar Hzami

doi:10.1016/j.crma.2013.07.021

Combinatorics

The indecomposable tournaments T with

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

Presented by: the Editorial Board

Houmem Belkhechine ¹; Imed Boudabbous ²; Kaouthar Hzami ³

¹ 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, Volume 351 (2013) no. 13-14, pp. 501-504

Abstract (Original language)
Résumé

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$ .

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$ .

Received: 2013-06-30
Accepted: 2013-07-31
Published online: 2013-07-01

DOI: 10.1016/j.crma.2013.07.021

Author's affiliations:

Houmem Belkhechine ¹; Imed Boudabbous ²; Kaouthar Hzami ³

¹ 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

@article{CRMATH_2013__351_13-14_501_0,
     author = {Houmem Belkhechine and Imed Boudabbous and Kaouthar Hzami},
     title = {The indecomposable tournaments {\protect\emph{T}} with $ |{W}_{5}(T)|=|T|-2$},
     journal = {Comptes Rendus. Math\'ematique},
     pages = {501--504},
     year = {2013},
     publisher = {Elsevier},
     volume = {351},
     number = {13-14},
     doi = {10.1016/j.crma.2013.07.021},
     language = {en},
}

TY  - JOUR
AU  - Houmem Belkhechine
AU  - Imed Boudabbous
AU  - Kaouthar Hzami
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
DO  - 10.1016/j.crma.2013.07.021
LA  - en
ID  - CRMATH_2013__351_13-14_501_0
ER  -

%0 Journal Article
%A Houmem Belkhechine
%A Imed Boudabbous
%A Kaouthar Hzami
%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
%R 10.1016/j.crma.2013.07.021
%G en
%F CRMATH_2013__351_13-14_501_0

Houmem Belkhechine; Imed Boudabbous; Kaouthar Hzami. 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

References
Cited by

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

[2] H. Belkhechine; I. Boudabbous; K. Hzami The indecomposable tournaments T with $| W_{5} (T) | = | T | - 2$ , 2013 | arXiv

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

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

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

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

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

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

Cited by Sources:

Comments - Policy