Tournois indécomposables et leurs sous-tournois indécomposables à six sommets

Boudabbous, Imed

doi:10.1016/j.crma.2015.03.021

Combinatoire

Tournois indécomposables et leurs sous-tournois indécomposables à six sommets

Présenté par : le comité de rédaction

Boudabbous, Imed ¹

¹ Université de Sfax, Institut préparatoire aux études d'ingénieurs de Sfax, Tunisie

Comptes Rendus. Mathématique, Tome 353 (2015) no. 8, pp. 671-675.

Résumé
Abstract

É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. On dit qu'un tournoi T abrite un tournoi $T^{'}$ si $T^{'}$ est isomorphe à un sous-tournoi de T. Dans cet article, nous classifions les tounois indécomposables à partir des tournois indécomposables à six sommets qu'ils abritent.

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. We say that a tournament $T^{'}$ embeds in a tournament T when $T^{'}$ is isomorphic to a subtournament of T. In this article, we classify the indecomposable tournaments according to the indecomposable tournaments with six vertices embedding in T.

Reçu le : 2014-07-05
Accepté le : 2015-03-19
Publié le : 2015-06-25

DOI : 10.1016/j.crma.2015.03.021

Affiliations des auteurs :

Boudabbous, Imed ¹

¹ Université de Sfax, Institut préparatoire aux études d'ingénieurs de Sfax, Tunisie

@article{CRMATH_2015__353_8_671_0,
     author = {Boudabbous, Imed},
     title = {Tournois ind\'ecomposables et leurs sous-tournois ind\'ecomposables \`a six sommets},
     journal = {Comptes Rendus. Math\'ematique},
     pages = {671--675},
     publisher = {Elsevier},
     volume = {353},
     number = {8},
     year = {2015},
     doi = {10.1016/j.crma.2015.03.021},
     language = {fr},
     url = {http://www.numdam.org/articles/10.1016/j.crma.2015.03.021/}
}

TY  - JOUR
AU  - Boudabbous, Imed
TI  - Tournois indécomposables et leurs sous-tournois indécomposables à six sommets
JO  - Comptes Rendus. Mathématique
PY  - 2015
SP  - 671
EP  - 675
VL  - 353
IS  - 8
PB  - Elsevier
UR  - http://www.numdam.org/articles/10.1016/j.crma.2015.03.021/
DO  - 10.1016/j.crma.2015.03.021
LA  - fr
ID  - CRMATH_2015__353_8_671_0
ER  -

%0 Journal Article
%A Boudabbous, Imed
%T Tournois indécomposables et leurs sous-tournois indécomposables à six sommets
%J Comptes Rendus. Mathématique
%D 2015
%P 671-675
%V 353
%N 8
%I Elsevier
%U http://www.numdam.org/articles/10.1016/j.crma.2015.03.021/
%R 10.1016/j.crma.2015.03.021
%G fr
%F CRMATH_2015__353_8_671_0

Boudabbous, Imed. Tournois indécomposables et leurs sous-tournois indécomposables à six sommets. Comptes Rendus. Mathématique, Tome 353 (2015) no. 8, pp. 671-675. doi : 10.1016/j.crma.2015.03.021. http://www.numdam.org/articles/10.1016/j.crma.2015.03.021/

Bibliographie
Cité par

[1] Belkhechine, H.; Boudabbous, I.; Dammak, J. Morphologie des tournois (–1)-critiques, C. R. Acad. Sci. Paris, Ser. I, Volume 345 (2007), pp. 663-666

[2] Boudabbous, Y.; Pouzet, M. The morphology of infinite tournaments; application to the growth of their profile, Eur. J. Comb., Volume 31 (2010) no. 2, pp. 461-481

[3] Boudabbous, Y.; Dammak, J.; Ille, P. Indecomposablity and duality of tournaments, Discrete Math., Volume 223 (2000), pp. 55-82

[4] Chudnovsky, M.; Seymour, P. Growing without cloning, SIAM J. Discrete Math., Volume 26 (2012), pp. 860-880

[5] Clarou, E.; Lopez, G. Configurations inévitables dans un tournoi indécomposable, C. R. Acad. Sci. Paris, Ser. I, Volume 324 (1997), pp. 1201-1204

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

[7] Ehrenfeucht, A.; Harju, T.; Rozenberg, G. The Theory of 2-Structures. A Framework for Decomposition and Transformation of Graphs, World Scientific, Singapore, 1999

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

[9] Gallai, T. Transitiv orientierbare Graphen, Acta Math. Acad. Sci. Hung., Volume 18 (1967), pp. 25-66

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

[11] Kantor, W.M. Automorphism groups of designs, Math. Z., Volume 109 (1969), pp. 246-252

[12] Latka, B.J. A structure theorem of tournaments omitting $N_{5}$ , J. Graph Theory, Volume 42 (2003), pp. 165-192

[13] Pouzet, M.; Zaguia, I. On minimal prime graphs and posets, Order, Volume 26 (2009) no. 4, pp. 357-375

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

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

^☆ Nous adressons nos vifs remerciements pour le rapporteur pour toutes ses remarques et suggestions qui ont bien amélioré la présentation de notre papier.

^☆☆ Ce travail a été supporté par le projet PHC : 14 MAG 14.