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.
Accepté le :
Publié le :
@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] La 5-reconstructibilité et l'indécomposabilité des relations binaires, Eur. J. Combin., Volume 23 (2002), pp. 507-522
[2] 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] Abritement entre relations, et spécialement entre chaînes, Symposi. Math., Instituto Nazionale di Alta Matematica, Volume 5 (1970), pp. 203-251
[5] L'indéformabilité des relations et multirelations binaires, Z. Math. Logik Grundlag. Math., Volume 24 (1978), pp. 303-317
[6] 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] A Collection of Mathematical Problems, Wiley, New York, 1960
Cité par Sources :
