Logique/Combinatoire
Sur les graphes 2-reconstructibles
Comptes Rendus. Mathématique, Tome 337 (2003) no. 7, pp. 437-440.

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 :
Accepté le :
Publié le :
DOI : 10.1016/j.crma.2003.08.002
Boussairi, Abderrahim 1 ; Chaichaa, Abdelhak 1

1 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 = {Boussairi, Abderrahim and Chaichaa, Abdelhak},
     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},
     url = {http://www.numdam.org/articles/10.1016/j.crma.2003.08.002/}
}
TY  - JOUR
AU  - Boussairi, Abderrahim
AU  - Chaichaa, Abdelhak
TI  - Sur les graphes 2-reconstructibles
JO  - Comptes Rendus. Mathématique
PY  - 2003
SP  - 437
EP  - 440
VL  - 337
IS  - 7
PB  - Elsevier
UR  - http://www.numdam.org/articles/10.1016/j.crma.2003.08.002/
DO  - 10.1016/j.crma.2003.08.002
LA  - fr
ID  - CRMATH_2003__337_7_437_0
ER  - 
%0 Journal Article
%A Boussairi, Abderrahim
%A Chaichaa, Abdelhak
%T Sur les graphes 2-reconstructibles
%J Comptes Rendus. Mathématique
%D 2003
%P 437-440
%V 337
%N 7
%I Elsevier
%U http://www.numdam.org/articles/10.1016/j.crma.2003.08.002/
%R 10.1016/j.crma.2003.08.002
%G fr
%F CRMATH_2003__337_7_437_0
Boussairi, Abderrahim; Chaichaa, Abdelhak. Sur les graphes 2-reconstructibles. Comptes Rendus. Mathématique, Tome 337 (2003) no. 7, pp. 437-440. doi : 10.1016/j.crma.2003.08.002. http://www.numdam.org/articles/10.1016/j.crma.2003.08.002/

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

[2] Boudabbous, Y.; Lopez, G. 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] 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

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

[6] Pouzet, M. 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] Ulam, S.M. A Collection of Mathematical Problems, Wiley, New York, 1960

Cité par Sources :