Sur les graphes 2-reconstructibles

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. To cite this article: A. Boussairi, A. Chaichaa, C. R. Acad. Sci. Paris, Ser. I 337 (2003).