Les tournois $ (⩽k)$-demi-reconstructibles pour $ k⩽6$

Boudabbous, Youssef; Boussaïri, Abderrahim; Chaïchaâ, Abdelhak; El Amri, Nadia

doi:10.1016/j.crma.2008.07.024

Logique/Combinatoire

Les tournois

(⩽ k)

-demi-reconstructibles pour

k ⩽ 6

Présenté par : Jean-Yves Girard

Boudabbous, Youssef ¹ ; Boussaïri, Abderrahim ² ; Chaïchaâ, Abdelhak ² ; El Amri, Nadia ¹

¹ Faculté des sciences de Sfax, BP 802, 3018 Sfax, Tunisie
² Faculté des sciences Aïn-Chock, département de mathématiques et informatique, Km 8 route d'El Jadida, BP 5366, Maarif, Casablanca, Maroc

Comptes Rendus. Mathématique, Tome 346 (2008) no. 17-18, pp. 919-924.

Résumé
Abstract

Soit $T = (S, A)$ un tournoi. Pour toute partie non vide X de S, on note $T [X]$ le sous-tournoi de T induit par X. Par ailleurs, le dual de T est le tournoi $T^{⋆}$ obtenu à partir de T en inversant tous ses arcs. Un tournoi $T^{'}$ est demi-isomorphe à T s'il est isomorphe à T ou à $T^{⋆}$ . Étant donné un entier $k ⩾ 1$ , deux tournois T et $T^{'}$ , ayant le même ensemble de sommets S, sont $(⩽ k)$ -demi-isomorphes lorsque pour toute partie non vide X de S ayant au plus k éléments, les sous-tournois $T [X]$ et $T^{'} [X]$ sont demi-isomorphes. Un tournoi T est $(⩽ k)$ -demi-reconstructible lorsque tout tournoi $(⩽ k)$ -demi-isomorphe à T lui est demi-isomorphe. En 1995, Y. Boudabbous et G. Lopez ont montré que les tournois sont $(⩽ 7)$ -demi-reconstructibles. Dans cette Note, nous caractérisons les tournois $(⩽ k)$ -demi-reconstructibles pour $3 ⩽ k ⩽ 6$ .

Let $T = (V, A)$ be a tournament. For a non-empty subset X of V, we denote by $T [X]$ the sub-tournament of T induced by X. The dual of T is the tournament $T^{⋆}$ obtained from T by reversing all its arcs. A tournament $T^{'}$ is half-isomorphic to T if it is isomorphic to T or $T^{⋆}$ . Given an integer $k ⩾ 1$ , two tournaments T, $T^{'}$ defined on the same set V are $(⩽ k)$ -half-isomorphic if for every non-empty subset X of V with at most k elements, the sub-tournaments $T [X]$ and $T^{'} [X]$ are half-isomorphic. A tournament T is $(⩽ k)$ -half-reconstructible provided that every tournament $T^{'}$ which is $(⩽ k)$ -half-isomorphic to T is half-isomorphic to it. In 1995, Y. Boudabbous and G. Lopez showed that the tournaments are $(⩽ 7)$ -half-reconstructible. In this Note, we characterize the $(⩽ k)$ -half-reconstructible tournameents for $3 ⩽ k ⩽ 6$ .

Reçu le : 2008-07-01
Accepté le : 2008-07-28
Publié le : 2008-08-27

DOI : 10.1016/j.crma.2008.07.024

Affiliations des auteurs :

Boudabbous, Youssef ¹ ; Boussaïri, Abderrahim ² ; Chaïchaâ, Abdelhak ² ; El Amri, Nadia ¹

@article{CRMATH_2008__346_17-18_919_0,
     author = {Boudabbous, Youssef and Boussa{\"\i}ri, Abderrahim and Cha{\"\i}cha\^a, Abdelhak and El Amri, Nadia},
     title = {Les tournois $ (\ensuremath{\leqslant}k)$-demi-reconstructibles pour $ k\ensuremath{\leqslant}6$},
     journal = {Comptes Rendus. Math\'ematique},
     pages = {919--924},
     publisher = {Elsevier},
     volume = {346},
     number = {17-18},
     year = {2008},
     doi = {10.1016/j.crma.2008.07.024},
     language = {fr},
     url = {http://www.numdam.org/articles/10.1016/j.crma.2008.07.024/}
}

TY  - JOUR
AU  - Boudabbous, Youssef
AU  - Boussaïri, Abderrahim
AU  - Chaïchaâ, Abdelhak
AU  - El Amri, Nadia
TI  - Les tournois $ (⩽k)$-demi-reconstructibles pour $ k⩽6$
JO  - Comptes Rendus. Mathématique
PY  - 2008
SP  - 919
EP  - 924
VL  - 346
IS  - 17-18
PB  - Elsevier
UR  - http://www.numdam.org/articles/10.1016/j.crma.2008.07.024/
DO  - 10.1016/j.crma.2008.07.024
LA  - fr
ID  - CRMATH_2008__346_17-18_919_0
ER  -

%0 Journal Article
%A Boudabbous, Youssef
%A Boussaïri, Abderrahim
%A Chaïchaâ, Abdelhak
%A El Amri, Nadia
%T Les tournois $ (⩽k)$-demi-reconstructibles pour $ k⩽6$
%J Comptes Rendus. Mathématique
%D 2008
%P 919-924
%V 346
%N 17-18
%I Elsevier
%U http://www.numdam.org/articles/10.1016/j.crma.2008.07.024/
%R 10.1016/j.crma.2008.07.024
%G fr
%F CRMATH_2008__346_17-18_919_0

Boudabbous, Youssef; Boussaïri, Abderrahim; Chaïchaâ, Abdelhak; El Amri, Nadia. Les tournois $ (⩽k)$-demi-reconstructibles pour $ k⩽6$. Comptes Rendus. Mathématique, Tome 346 (2008) no. 17-18, pp. 919-924. doi : 10.1016/j.crma.2008.07.024. http://www.numdam.org/articles/10.1016/j.crma.2008.07.024/

Bibliographie
Cité par

[1] Boudabbous, Y. La 5-reconstructibilité et l'indécomposabilité des relations binaires, Eur. J. Combinatorics, Volume 23 (2002), pp. 507-522

[2] Boudabbous, Y.; Lopez, G. La relation différence et l'anti-isomorphie, Math. Logic Quart., Volume 41 (1995), pp. 268-280

[3] Boudabbous, Y.; Lopez, G. The minimal non- $(⩽ k)$ -reconstructible relations, Discrete Math., Volume 291 (2005), pp. 19-40

[4] Boussaïri, A.; Ille, P.; Lopez, G.; Thomassé, S. The C₃-structure of tournaments, Discrete Math., Volume 277 (2004), pp. 29-43

[5] Fraïssé, R. Abritement entre relations et spécialement entre chaînes, Symposi. Math., Instituto Nazionale di Alta Matematica, Volume 5 (1970), pp. 203-251

[6] Gallai, T. Transitiv orientierbare graphen, Acta Math. Acad. Sci. Hungar., Volume 18 (1967), pp. 25-66

[7] Hagendorf, J.G.; Lopez, G. La demi-reconstructibilité des relations binaires d'au moins 13 éléments, C. R. Acad. Sci. Paris, Ser. I, Volume 317 (1993), pp. 7-12

[8] Lopez, G. Deux résultats concernant la détermination d'une relation par les types d'isomorphie de ses restrictions, C. R. Acad. Sci. Paris, Ser. A, Volume 274 (1972), pp. 1525-1528

[9] Lopez, G. L'indéformabilité des relations et multirelations binaires, Z. Math. Logik Grundlag. Math., Volume 24 (1978), pp. 303-317

Cité par Sources :