Morphologie des tournois (−1)-critiques

Belkhechine, Houmem; Boudabbous, Imed; Dammak, Jamel

doi:10.1016/j.crma.2007.11.006

Combinatoire/Logique

Morphologie des tournois (−1)-critiques
[Morphology of the

(- 1)

-critical tournaments]

Presented by: Jean-Yves Girard

Belkhechine, Houmem ¹; Boudabbous, Imed ²; Dammak, Jamel ³

¹ Faculté des sciences de Gabès, cité Riadh, Zirig 6072 Gabès, Tunisie
² Institut préparatoire aux études d'ingénieurs de Sfax, route Menzel-Chaker Km 0.5, 3018 Sfax, Tunisie
³ Faculté des sciences de Sfax, BP 802, 3018 Sfax, Tunisie

Comptes Rendus. Mathématique, Volume 345 (2007) no. 12, pp. 663-666.

Abstract
Résumé

Given a tournament $T = (V, A)$ , a subset X of V is an interval of T provided that for any $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, all the intervals of which are trivial, is indecomposable; otherwise, it is decomposable. A vertex x of an indecomposable tournament is critical if $T - x$ is decomposable. In 1993, J.H. Schmerl and W.T. Trotter characterized the tournaments, all the vertices of which are critical, called critical tournaments. The cardinality of these tournaments is odd. Given an odd integer $m ⩾ 5$ , there exist three critical tournaments of cardinality m. In this article, we characterize the tournaments which admit a single non critical vertex, that we call $(- 1)$ -critical tournaments. The cardinality of these tournaments is odd. Given an odd integer $m ⩾ 7$ , there exist $3 m - 15$ $(- 1)$ -critical tournaments of cardinality m. Our work extends a recent study of indecomposability and critical vertices made by Y. Boudabbous and P. Ille.

Étant donné un tournoi $T = (S, A)$ , 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 ; sinon, il est décomposable. Un sommet x d'un tournoi indécomposable T est critique si le tournoi $T - x$ est décomposable. En 1993, J.H. Schmerl et W.T. Trotter ont caractérisé les tournois dont tous les sommets sont critiques, appelés tournois critiques. Ces tournois ont un cardinal impair ⩾5. Pour chaque entier impair $m ⩾ 5$ , il existe trois tournois critiques de cardinal m. Dans cet article, nous caractérisons les tournois qui admettent un unique sommet non critique, que nous appelons tournois (−1)-critiques. Ces tournois ont un cardinal impair ⩾7. Pour chaque entier impair $m ⩾ 7$ , il existe $3 m - 15$ tournois $(- 1)$ -critiques de cardinal m. Notre travail prolonge une étude récente sur l'indécomposabilité et les sommets critiques faite par Y. Boudabbous et P. Ille.

Received: 2007-10-11
Accepted: 2007-10-29
Published online: 2007-11-28

DOI: 10.1016/j.crma.2007.11.006

Author's affiliations:

Belkhechine, Houmem ¹; Boudabbous, Imed ²; Dammak, Jamel ³

@article{CRMATH_2007__345_12_663_0,
     author = {Belkhechine, Houmem and Boudabbous, Imed and Dammak, Jamel},
     title = {Morphologie des tournois (\ensuremath{-}1)-critiques},
     journal = {Comptes Rendus. Math\'ematique},
     pages = {663--666},
     publisher = {Elsevier},
     volume = {345},
     number = {12},
     year = {2007},
     doi = {10.1016/j.crma.2007.11.006},
     language = {fr},
     url = {https://www.numdam.org/articles/10.1016/j.crma.2007.11.006/}
}

TY  - JOUR
AU  - Belkhechine, Houmem
AU  - Boudabbous, Imed
AU  - Dammak, Jamel
TI  - Morphologie des tournois (−1)-critiques
JO  - Comptes Rendus. Mathématique
PY  - 2007
SP  - 663
EP  - 666
VL  - 345
IS  - 12
PB  - Elsevier
UR  - https://www.numdam.org/articles/10.1016/j.crma.2007.11.006/
DO  - 10.1016/j.crma.2007.11.006
LA  - fr
ID  - CRMATH_2007__345_12_663_0
ER  -

%0 Journal Article
%A Belkhechine, Houmem
%A Boudabbous, Imed
%A Dammak, Jamel
%T Morphologie des tournois (−1)-critiques
%J Comptes Rendus. Mathématique
%D 2007
%P 663-666
%V 345
%N 12
%I Elsevier
%U https://www.numdam.org/articles/10.1016/j.crma.2007.11.006/
%R 10.1016/j.crma.2007.11.006
%G fr
%F CRMATH_2007__345_12_663_0

Belkhechine, Houmem; Boudabbous, Imed; Dammak, Jamel. Morphologie des tournois (−1)-critiques. Comptes Rendus. Mathématique, Volume 345 (2007) no. 12, pp. 663-666. doi : 10.1016/j.crma.2007.11.006. https://www.numdam.org/articles/10.1016/j.crma.2007.11.006/

References
Cited by

[1] Boudabbous, I.; Ille, P. Critical and infinite directed graphs, Discrete Math., Volume 307 (2007), pp. 2415-2428

[2] Y. Boudabbous, P. Ille, Indecomposability graph and critical vertices of an indecomposable graph, soumis à Discrete Math

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

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

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

[6] Ille, P. Recognition problem in reconstruction for decomposable relations (Sands, B.; Sauer, N.; Woodrow, R., eds.), Finite and Infinite Combinatorics in Sets and Logic, Kluwer Academic Publishers, 1993, pp. 189-198

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