La -demi-reconstructibilité des graphes pour - 19/08/08
pages | 4 |
Iconographies | 0 |
Vidéos | 0 |
Autres | 0 |
Résumé |
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. Pour citer cet article : N. El Amri, C. R. Acad. Sci. Paris, Ser. I 346 (2008).
Le texte complet de cet article est disponible en PDF.Abstract |
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. To cite this article: N. El Amri, C. R. Acad. Sci. Paris, Ser. I 346 (2008).
Le texte complet de cet article est disponible en PDF.Plan
Vol 346 - N° 13-14
P. 707-710 - juillet 2008 Retour au numéroBienvenue sur EM-consulte, la référence des professionnels de santé.
L’accès au texte intégral de cet article nécessite un abonnement.
Bienvenue sur EM-consulte, la référence des professionnels de santé.
L’achat d’article à l’unité est indisponible à l’heure actuelle.
Déjà abonné à cette revue ?