[The -half-reconstructibility of graphs for ]
Let be a graph. For every subset X of V is associated the subgraph of G induced by X. The dual of G is the graph such that, . A graph is half-isomorphic to G if it is isomorphic to G or . Let k be a non negative integer. A graph defined on the same vertex set V of G is -half-isomorphic to G if for all subset X of V on at most k elements, the subgraphs and are half-isomorphic. G is called -half-reconstructible provided that every graph which is -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 -half-reconstructible. After that, in 2003, J. Dammak characterized the -half-reconstructible finite graphs. In this Note we study the general case of graphs (finite and infinite). We characterize the -half-reconstructible infinite graphs. Then, we extend the study made by J. Dammak to infinite graphs by characterizing the -half-reconstructible infinite graphs.
Soit un graphe . Pour toute partie X de S est associé le sous-graphe de G induit par X. Le dual de G est le graphe où, . Un graphe est demi-isomorphe à G, s'il est isomorphe à G ou à . Soit un entier . Un graphe , ayant le même ensemble de sommets S que G, est -demi-isomorphe à G lorsque pour toute partie X de S ayant au plus k sommets, les sous-graphes et sont demi-isomorphes. Le graphe G est -demi-reconstructible lorsque tout graphe -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 -demi-reconstructibles. Ensuite, en 2003, J. Dammak a caractérisé les graphes finis -demi-reconstructibles. Dans cette Note nous étudions le cas général des graphes (finis et infinis). Nous caractérisons les graphes infinis -demi-reconstructibles. Ensuite, nous étendons l'étude de J. Dammak aux graphes infinis en caractérisant les graphes -demi-reconstructibles.
Accepted:
Published online:
Nadia El Amri 1
@article{CRMATH_2008__346_13-14_707_0, author = {Nadia El Amri}, title = {La $ (\ensuremath{\leqslant}k)$-demi-reconstructibilit\'e des graphes pour $ k\in \{11,12\}$}, journal = {Comptes Rendus. Math\'ematique}, pages = {707--710}, publisher = {Elsevier}, volume = {346}, number = {13-14}, year = {2008}, doi = {10.1016/j.crma.2008.04.012}, language = {fr}, }
Nadia El Amri. La $ (⩽k)$-demi-reconstructibilité des graphes pour $ k\in \{11,12\}$. Comptes Rendus. Mathématique, Volume 346 (2008) no. 13-14, pp. 707-710. doi : 10.1016/j.crma.2008.04.012. https://comptes-rendus.academie-sciences.fr/mathematique/articles/10.1016/j.crma.2008.04.012/
[1] Y. Boudabbous, C. Delhommé, Prechains and k-selfduality, preprint, 2008
[2] Y. Boudabbous, C. Delhommé, k-reconstructible binary relations, preprint, 2008
[3] Caractérisation des relations binaires finies d-demi-reconstructibles, Proyecciones, Volume 22 (2003) no. 1, pp. 31-61
[4] Abritement entre relations et spécialement entre chaînes, Symposi. Math., Instituto Nazionale di Alta Matematica, Volume 5 (1970), pp. 203-251
[5] La demi-reconstructibilité des relations binaires d'au moins 13 éléments, C. R. Acad. Sci. Paris, Ser. I, Volume 317 (1993), pp. 7-12
[6] Deux résultats concernant la détermination d'une relation par les types d'isomorphie de ses restrictions, C. R. Acad. Sci. Paris, Sér. A, Volume 274 (1972), pp. 1525-1528
[7] L'indéformabilité des relations et multirelations binaires, Z. Math. Logik Grundlag. Math., Volume 24 (1978), pp. 303-317
[8] Reconstruction of binary relations from their restrictions of cardinality 2, 3, 4 and (). I, Z. Math. Logik Grundlag. Math., Volume 38 (1992), pp. 27-37
Cited by Sources:
Comments - Policy