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

Imed Boudabbous

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

Imed Boudabbous ¹

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

Comptes Rendus. Mathématique, Volume 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 :

Imed Boudabbous ¹

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

@article{CRMATH_2015__353_8_671_0,
     author = {Imed Boudabbous},
     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},
}

TY  - JOUR
AU  - Imed Boudabbous
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
DO  - 10.1016/j.crma.2015.03.021
LA  - fr
ID  - CRMATH_2015__353_8_671_0
ER  -

%0 Journal Article
%A Imed Boudabbous
%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
%R 10.1016/j.crma.2015.03.021
%G fr
%F CRMATH_2015__353_8_671_0

Imed Boudabbous. Tournois indécomposables et leurs sous-tournois indécomposables à six sommets. Comptes Rendus. Mathématique, Volume 353 (2015) no. 8, pp. 671-675. doi : 10.1016/j.crma.2015.03.021. https://comptes-rendus.academie-sciences.fr/mathematique/articles/10.1016/j.crma.2015.03.021/

Bibliographie
Cité par

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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.

Commentaires - Politique