Sur les graphes 2-reconstructibles

Abderrahim Boussairi; Abdelhak Chaichaa

doi:10.1016/j.crma.2003.08.002

Logique/Combinatoire

Sur les graphes 2-reconstructibles

Présenté par : Jean-Yves Girard

Abderrahim Boussairi ¹ ; Abdelhak Chaichaa ¹

¹ Université Hassan II, faculté des sciences Ain Chock, département de mathématiques et informatique, km 8 route d'El Jadida, BP 5366, Maarif, Casablanca, Maroc

Comptes Rendus. Mathématique, Volume 337 (2003) no. 7, pp. 437-440.

Résumé
Abstract

Soit k un entier (k⩾1) et G=(V,E) un graphe ayant au moins k sommets, un graphe G′=(V,E′) est une k-reconstruction de G si pour toute partie W de V à k éléments, les sous-graphes G(W) et G′(W) induits par W sont isomorphes. Le graphe G est k-reconstructible, lorsque toute k-reconstruction de G est isomorphe à G. Lopez (Z. Math. Logik Grundlag. Math. 24 (1978) 303–317) a prouvé que tout graphe est 6-reconstructible. Pour k=3,4 et 5, les graphes k-reconstructibles ont été étudiés dans Boudabbous et Lopez (Eur. J. Combin. 23 (2002) 507–522 ; C. R. Acad. Sci. Paris, Sér. I 329 (1999) 845–848). Dans cette Note, nous introduisons un groupe de permutations permettant d'interpréter la 2-reconstructibilité et nous caractérisons les graphes qui s'abritent dans un graphe 2-reconstructible.

Let k be an integer (k⩾1) and G=(V,E) a graph with more than k vertices, a graph G′=(V,E′) is a k-reconstruction of G if, for any subset W of V with k elements, the subgraphs G(W) and G′(W) induced by W are isomorphic. The graph G is k-reconstructible when each k-reconstruction of G is isomorphic to G. Lopez (Z. Math. Logik Grundlag. Math. 24 (1978) 303–317) proved that any graph is 6-reconstructible. For k=3,4 and 5, the k-reconstructible graphs were studied in Boudabbous and Lopez (Eur. J. Combin. 23 (2002) 507–522; C. R. Acad. Sci. Paris, Sér. I 329 (1999) 845–848). In this Note, we introduce a permutations group allowing for the interpretation of the 2-reconstructibility and we characterize the graphs which are embedded in a 2-reconstructible graph.

Reçu le : 2003-07-31
Accepté le : 2003-08-27
Publié le : 2003-10-01

DOI : 10.1016/j.crma.2003.08.002

Affiliations des auteurs :

Abderrahim Boussairi ¹ ; Abdelhak Chaichaa ¹

¹ Université Hassan II, faculté des sciences Ain Chock, département de mathématiques et informatique, km 8 route d'El Jadida, BP 5366, Maarif, Casablanca, Maroc

@article{CRMATH_2003__337_7_437_0,
     author = {Abderrahim Boussairi and Abdelhak Chaichaa},
     title = {Sur les graphes 2-reconstructibles},
     journal = {Comptes Rendus. Math\'ematique},
     pages = {437--440},
     publisher = {Elsevier},
     volume = {337},
     number = {7},
     year = {2003},
     doi = {10.1016/j.crma.2003.08.002},
     language = {fr},
}

TY  - JOUR
AU  - Abderrahim Boussairi
AU  - Abdelhak Chaichaa
TI  - Sur les graphes 2-reconstructibles
JO  - Comptes Rendus. Mathématique
PY  - 2003
SP  - 437
EP  - 440
VL  - 337
IS  - 7
PB  - Elsevier
DO  - 10.1016/j.crma.2003.08.002
LA  - fr
ID  - CRMATH_2003__337_7_437_0
ER  -

%0 Journal Article
%A Abderrahim Boussairi
%A Abdelhak Chaichaa
%T Sur les graphes 2-reconstructibles
%J Comptes Rendus. Mathématique
%D 2003
%P 437-440
%V 337
%N 7
%I Elsevier
%R 10.1016/j.crma.2003.08.002
%G fr
%F CRMATH_2003__337_7_437_0

Abderrahim Boussairi; Abdelhak Chaichaa. Sur les graphes 2-reconstructibles. Comptes Rendus. Mathématique, Volume 337 (2003) no. 7, pp. 437-440. doi : 10.1016/j.crma.2003.08.002. https://comptes-rendus.academie-sciences.fr/mathematique/articles/10.1016/j.crma.2003.08.002/

Bibliographie
Cité par

[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 Procédé de construction des relations binaires non (⩽3)-reconstructibles, C. R. Acad. Sci. Paris, Ser. I, Volume 329 (1999), pp. 845-848

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

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

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

[6] M. Pouzet Application d'une propriété combinatoire des parties d'un ensemble aux groupes et aux relations, Math. Z., Volume 150 (1976), pp. 117-134

[7] S.M. Ulam A Collection of Mathematical Problems, Wiley, New York, 1960

Cité par Sources :

Commentaires - Politique