La (⩽k)-demi-reconstructibilité des graphes pour k∈{11,12}

RésuméSoit un graphe G=(S,A). Pour toute partie X de S est associé le sous-graphe G(X)=(X,A∩(X×X)) de G induit par X. Le dual de G est le graphe G*=(S,A*) où, . Un graphe G′ est demi-isomorphe à G, s'il est isomorphe à G ou à G*. Soit un entier k⩾1. Un graphe G′, ayant le même ensemble de sommets S que G, est (⩽k)-demi-isomorphe à G lorsque pour toute partie X de S ayant au plus k sommets, les sous-graphes G(X) et G′(X) sont demi-isomorphes. Le graphe G est (⩽k)-demi-reconstructible lorsque tout graphe (⩽k)-demi-isomorphe à G lui est demi-isomorphe. J. G. Hagendorf élargit ainsi, en 1993, la problématique de la reconstruction à la demi-reconstruction. J. G. Hagendorf et G. Lopez ont montré que les graphes finis sont (⩽12)-demi-reconstructibles. Ensuite, en 2003, J. Dammak a caractérisé les graphes finis (⩽11)-demi-reconstructibles. Dans cette Note nous étudions le cas général des graphes (finis et infinis). Nous caractérisons les graphes infinis (⩽12)-demi-reconstructibles. Ensuite, nous étendons l'étude de J. Dammak aux graphes infinis en caractérisant les graphes (⩽11)-demi-reconstructibles. Pour citer cet article : N. El Amri, C. R. Acad. Sci. Paris, Ser. I 346 (2008).

Let G=(V,A) be a graph. For every subset X of V is associated the subgraph G(X)=(X,A∩(X×X)) of G induced by X. The dual of G is the graph G*=(V,A*) such that, . A graph G′ is half-isomorphic to G if it is isomorphic to G or G*. Let k be a non negative integer. A graph G′ defined on the same vertex set V of G is (⩽k)-half-isomorphic to G if for all subset X of V on at most k elements, the subgraphs G(X) and G′(X) are half-isomorphic. G is called (⩽k)-half-reconstructible provided that every graph G′ which is (⩽k)-half-isomorphic to G is half-isomorphic to G. In 1993 J. G. Hagendorf expanded the reconstruction problematic to the half-reconstruction. J. G. Hagendorf and G. Lopez showed that the finite graphs are (⩽12)-half-reconstructible. After that, in 2003, J. Dammak characterized the (⩽11)-half-reconstructible finite graphs. In this Note we study the general case of graphs (finite and infinite). We characterize the (⩽12)-half-reconstructible infinite graphs. Then, we extend the study made by J. Dammak to infinite graphs by characterizing the (⩽11)-half-reconstructible infinite graphs. To cite this article: N. El Amri, C. R. Acad. Sci. Paris, Ser. I 346 (2008).