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

Nadia El Amri

doi:10.1016/j.crma.2008.04.012

Logique/Combinatoire

La

(⩽ k)

-demi-reconstructibilité des graphes pour

k \in {11, 12}

[The

(⩽ k)

-half-reconstructibility of graphs for

k \in {11, 12}

]

Presented by: Jean-Yves Girard

Nadia El Amri ¹

¹ Faculté des sciences de Sfax, BP 802, 3018 Sfax, Tunisie

Comptes Rendus. Mathématique, Volume 346 (2008) no. 13-14, pp. 707-710.

Résumé (Original language)
Abstract

Soit un graphe $G = (S, A)$ . Pour toute partie X de S est associé le sous-graphe $G (X) = (X, A \cap (X \times X))$ de G induit par X. Le dual de G est le graphe $G^{*} = (S, A^{*})$ où, $A^{*} = {(x, y) : (y, x) \in A}$ . 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.

Let $G = (V, A)$ be a graph. For every subset X of V is associated the subgraph $G (X) = (X, A \cap (X \times X))$ of G induced by X. The dual of G is the graph $G^{*} = (V, A^{*})$ such that, $A^{*} = {(x, y) : (y, x) \in A}$ . 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.

Received: 2008-03-27
Accepted: 2008-04-14
Published online: 2008-05-27

DOI: 10.1016/j.crma.2008.04.012

Author's affiliations:

Nadia El Amri ¹

¹ Faculté des sciences de Sfax, BP 802, 3018 Sfax, Tunisie

@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},
}

TY  - JOUR
AU  - Nadia El Amri
TI  - La $ (⩽k)$-demi-reconstructibilité des graphes pour $ k\in \{11,12\}$
JO  - Comptes Rendus. Mathématique
PY  - 2008
SP  - 707
EP  - 710
VL  - 346
IS  - 13-14
PB  - Elsevier
DO  - 10.1016/j.crma.2008.04.012
LA  - fr
ID  - CRMATH_2008__346_13-14_707_0
ER  -

%0 Journal Article
%A Nadia El Amri
%T La $ (⩽k)$-demi-reconstructibilité des graphes pour $ k\in \{11,12\}$
%J Comptes Rendus. Mathématique
%D 2008
%P 707-710
%V 346
%N 13-14
%I Elsevier
%R 10.1016/j.crma.2008.04.012
%G fr
%F CRMATH_2008__346_13-14_707_0

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/

References
Cited by

[1] Y. Boudabbous, C. Delhommé, Prechains and k-selfduality, preprint, 2008

[2] Y. Boudabbous, C. Delhommé, k-reconstructible binary relations, preprint, 2008

[3] J. Dammak Caractérisation des relations binaires finies d-demi-reconstructibles, Proyecciones, Volume 22 (2003) no. 1, pp. 31-61

[4] R. Fraïssé Abritement entre relations et spécialement entre chaînes, Symposi. Math., Instituto Nazionale di Alta Matematica, Volume 5 (1970), pp. 203-251

[5] J.G. Hagendorf; G. Lopez 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] G. Lopez 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] G. Lopez L'indéformabilité des relations et multirelations binaires, Z. Math. Logik Grundlag. Math., Volume 24 (1978), pp. 303-317

[8] G. Lopez; C. Rauzy Reconstruction of binary relations from their restrictions of cardinality 2, 3, 4 and ( $n - 1$ ). I, Z. Math. Logik Grundlag. Math., Volume 38 (1992), pp. 27-37

Cited by Sources:

Comments - Policy