Comptes Rendus
no. 1
Logique/Combinatoire
Les graphes 2-reconstructibles indécomposables

Présenté par : Jean-Yves Girard

Abderrahim Boussaïri1 ; Abdelhak Chaïchaâ1
1 Université Hassan II, 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, Volume 345 (2007) no. 1, pp. 1-4.

Un graphe (orienté) G est 2-reconstructible si tout graphe H obtenu à partir de G en inversant l'orientation de certaines de ses paires orientées, choisies arbitrairement, est isomorphe à G. Soit G un graphe 2-reconstructible, indécomposable, ayant r paires orientées. Il découle des résultats obtenus dans Boussairi et Chaichaa (2003) que G possède au moins 2r+1 sommets. Dans cette Note, nous déterminons, en fonction de r, le nombre minimum de sommets de G.

A (direct) graph G is 2-reconstructible if any graph H obtained from G by reversing the orientation of some of its directed pairs, chosen arbitrarily, is isomorphic to G. Let G be a 2-reconstructible indecomposable graph, with r directed pairs. It follows from the results of Boussairi and Chaichaa (2003) that G has at least 2r+1 vertices. In this Note, we determine, in terms of r, the minimum number of vertices of G.

Reçu le :
Accepté le :
Publié le :
DOI : 10.1016/j.crma.2007.05.028
Abderrahim Boussaïri 1 ; Abdelhak Chaïchaâ 1

1 Université Hassan II, 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_2007__345_1_1_0,
     author = {Abderrahim Boussa{\"\i}ri and Abdelhak Cha{\"\i}cha\^a},
     title = {Les graphes 2-reconstructibles ind\'ecomposables},
     journal = {Comptes Rendus. Math\'ematique},
     pages = {1--4},
     publisher = {Elsevier},
     volume = {345},
     number = {1},
     year = {2007},
     doi = {10.1016/j.crma.2007.05.028},
     language = {fr},
}
TY  - JOUR
AU  - Abderrahim Boussaïri
AU  - Abdelhak Chaïchaâ
TI  - Les graphes 2-reconstructibles indécomposables
JO  - Comptes Rendus. Mathématique
PY  - 2007
SP  - 1
EP  - 4
VL  - 345
IS  - 1
PB  - Elsevier
DO  - 10.1016/j.crma.2007.05.028
LA  - fr
ID  - CRMATH_2007__345_1_1_0
ER  - 
%0 Journal Article
%A Abderrahim Boussaïri
%A Abdelhak Chaïchaâ
%T Les graphes 2-reconstructibles indécomposables
%J Comptes Rendus. Mathématique
%D 2007
%P 1-4
%V 345
%N 1
%I Elsevier
%R 10.1016/j.crma.2007.05.028
%G fr
%F CRMATH_2007__345_1_1_0
Abderrahim Boussaïri; Abdelhak Chaïchaâ. Les graphes 2-reconstructibles indécomposables. Comptes Rendus. Mathématique, Volume 345 (2007) no. 1, pp. 1-4. doi : 10.1016/j.crma.2007.05.028. https://comptes-rendus.academie-sciences.fr/mathematique/articles/10.1016/j.crma.2007.05.028/

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

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

[3] Y. Boudabbous, G. Lopez, Communication privée, 2002

[4] A. Boussairi; A. Chaichaa Sur les graphes 2-reconstructibles, C. R. Acad. Sci. Paris, Ser. I, Volume 337 (2003), pp. 437-440

[5] J.D. Dixon; B. Mortimer Permutation Groups, Springer, 1996

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

Cité par Sources :

Commentaires - Politique

Ces articles pourraient vous intéresser

Sur les graphes 2-reconstructibles

Abderrahim Boussairi; Abdelhak Chaichaa

C. R. Math (2003)

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

Youssef Boudabbous; Abderrahim Boussaïri; Abdelhak Chaïchaâ; ...

C. R. Math (2008)

The (⩽6)-half-reconstructibility of digraphs

Jamel Dammak; Baraa Salem

C. R. Math (2014)