Geodesic
Logique/Combinatoire
Les tournois (⩽k)-demi-reconstructibles pour k⩽6
Présenté par : Jean-Yves Girard
Boudabbous, Youssef1 ; Boussaïri, Abderrahim2 ; Chaïchaâ, Abdelhak2 ; El Amri, Nadia1
1 Faculté des sciences de Sfax, BP 802, 3018 Sfax, Tunisie
2 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 Cet article a éte moissonné depuis la source Numdam

Voir la notice de l'article

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 :
Accepté le :
Publié le :
DOI : 10.1016/j.crma.2008.07.024

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

1 Faculté des sciences de Sfax, BP 802, 3018 Sfax, Tunisie
2 Faculté des sciences Aïn-Chock, département de mathématiques et informatique, Km 8 route d'El Jadida, BP 5366, Maarif, Casablanca, Maroc 
@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},
     year = {2008},
     publisher = {Elsevier},
     volume = {346},
     number = {17-18},
     doi = {10.1016/j.crma.2008.07.024},
     language = {fr},
     url = {http://geodesic.mathdoc.fr/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://geodesic.mathdoc.fr/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://geodesic.mathdoc.fr/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

Cité par Sources :