Combinatorics
The (⩽6)-half-reconstructibility of digraphs
[La (⩽6)-demi-reconstructibilité des graphes orientés]

Présenté par : the Editorial Board

Dammak, Jamel1 ; Salem, Baraa1
1 Département de Mathématiques, Faculté des Sciences de Sfax, BP 802, 3018 Sfax, Tunisia
Comptes Rendus. Mathématique, Tome 352 (2014) no. 7-8, pp. 541-545.

Soit G=(V,A) un graphe orienté. À toute partie X de V, on associe le sous-graphe orienté G[X]=(X,A∩(X×X)) de G induit par X. Étant donné un entier naturel non nul k, un graphe orienté G est (⩽k)-demi-reconstructible s'il est déterminé à la dualité près par ses sous-graphes de cardinalité ⩽k. En 2003, J. Dammak a caractérisé les graphes orientés finis qui sont (⩽k)-demi-reconstructibles, pour k∈{7,8,9,10,11}. Ensuite, N. El Amri a étendu la caractérisation de J. Dammak pour les graphes orientés infinis. Dans cette note, nous caractérisons les graphes orientés (⩽6)-demi-reconstructibles.

Let G=(V,A) be a digraph. With every subset X of V, we associate the subdigraph G[X]=(X,A∩(X×X)) of G induced by X. Given a positive integer k, a digraph G is (⩽k)-half-reconstructible if it is determined up to duality by its subdigraphs of cardinality ⩽k. In 2003, J. Dammak characterized the (⩽k)-half-reconstructible finite digraphs, for k∈{7,8,9,10,11}. N. El Amri extended J. Dammak's characterization to infinite digraphs. In this paper, we characterize the (⩽6)-half-reconstructible digraphs.

Reçu le :
Accepté le :
Publié le :
DOI : 10.1016/j.crma.2014.03.009
Dammak, Jamel 1 ; Salem, Baraa 1

1 Département de Mathématiques, Faculté des Sciences de Sfax, BP 802, 3018 Sfax, Tunisia 
@article{CRMATH_2014__352_7-8_541_0,
     author = {Dammak, Jamel and Salem, Baraa},
     title = {The $ (\ensuremath{\leqslant}6)$-half-reconstructibility of digraphs},
     journal = {Comptes Rendus. Math\'ematique},
     pages = {541--545},
     publisher = {Elsevier},
     volume = {352},
     number = {7-8},
     year = {2014},
     doi = {10.1016/j.crma.2014.03.009},
     language = {en},
     url = {https://www.numdam.org/articles/10.1016/j.crma.2014.03.009/}
}
TY  - JOUR
AU  - Dammak, Jamel
AU  - Salem, Baraa
TI  - The $ (⩽6)$-half-reconstructibility of digraphs
JO  - Comptes Rendus. Mathématique
PY  - 2014
SP  - 541
EP  - 545
VL  - 352
IS  - 7-8
PB  - Elsevier
UR  - https://www.numdam.org/articles/10.1016/j.crma.2014.03.009/
DO  - 10.1016/j.crma.2014.03.009
LA  - en
ID  - CRMATH_2014__352_7-8_541_0
ER  - 
%0 Journal Article
%A Dammak, Jamel
%A Salem, Baraa
%T The $ (⩽6)$-half-reconstructibility of digraphs
%J Comptes Rendus. Mathématique
%D 2014
%P 541-545
%V 352
%N 7-8
%I Elsevier
%U https://www.numdam.org/articles/10.1016/j.crma.2014.03.009/
%R 10.1016/j.crma.2014.03.009
%G en
%F CRMATH_2014__352_7-8_541_0
Dammak, Jamel; Salem, Baraa. The $ (⩽6)$-half-reconstructibility of digraphs. Comptes Rendus. Mathématique, Tome 352 (2014) no. 7-8, pp. 541-545. doi : 10.1016/j.crma.2014.03.009. https://www.numdam.org/articles/10.1016/j.crma.2014.03.009/

[1] Bondy, J.A. A graph reconstructor's manual, Guildford (Lond. Math. Soc. Lect. Note Ser.), Volume vol. 166, Cambridge Univ. Press, Cambridge (1991), pp. 221-252

[2] Bondy, J.A.; Hemminger, R.L. Graph reconstruction, a survey, J. Graph Theory, Volume 1 (1977) no. 3, pp. 27-268

[3] Bouaziz, M.; Boudabbous, Y.; El Amri, N. Hereditary hemimorphy of {−k}-hemimorphic tournaments for k⩾5, J. Korean Math. Soc., Volume 48 (2011) no. 3, pp. 599-626

[4] Boudabbous, Y. La 5-reconstructibilité et l'indécomposabilité des relations binaires, Eur. J. Comb., Volume 23 (2002), pp. 507-522

[5] Boudabbous, Y. Isomorphie héréditaire et {−4}-hypomorphie pour les tournois, C. R. Acad. Sci. Paris, Ser. I, Volume 347 (2009), pp. 841-844

[6] Boudabbous, Y.; Boussairi, A.; Chaïchaâ, A.; El Amri, N. Les tournois (⩽k)-demi-reconstructibles pour k⩽6, C. R. Acad. Sci. Paris, Ser. I, Volume 346 (2008), pp. 919-924

[7] Boudabbous, Y.; Dammak, J. Sur la {−k} demi-reconstructibilité des tournois finis, C. R. Acad. Sci. Paris, Ser. I, Volume 326 (1998), pp. 1037-1040

[8] Boudabbous, Y.; Delhommé, C. Prechains and self duality, Discrete Math., Volume 312 (2012), pp. 1743-1765

[9] Boudabbous, Y.; Lopez, G. La relation différence et l'anti-isomorphie, Math. Logic Quart., Volume 41 (1995) no. 2, pp. 268-280

[10] Boudabbous, Y.; Lopez, G. The minimal non-(⩽k)-reconstructible relations, Discrete Math., Volume 291 (2005), pp. 19-40

[11] Dammak, J. La dualité dans la demi-reconstruction des relations binaires finies, C. R. Acad. Sci. Paris, Ser. I, Volume 327 (1998), pp. 861-864

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

[13] Dammak, J. La (−5)-demi-reconstructibilité des relations binaires connexes finies, Proycciones, Volume 22 (2003) no. 3, pp. 181-199

[14] N. El Amri, La (⩽k)-demi-reconstructibilité des graphes pour 7⩽k⩽12, to appear in Ars Comb., accepted in 2010.

[15] Fraïssé, R. Abritement entre relations et spécialement entre chaînes, INDAM, Rome, 1969/70, Academic Press, London (1971), pp. 203-251

[16] Hagendorf, J.G.; Lopez, G. 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

[17] Ille, P. La reconstructibilité des relations binaires, C. R. Acad. Sci. Paris, Ser. I, Volume 306 (1988), pp. 635-638

[18] Lopez, G. Deux résultats concernant la détermination d'une relation par les types d'isomorphie de ses restrictions, C. R. Acad. Sci. Paris, Ser. A, Volume 274 (1972), pp. 1525-1528

[19] Lopez, G. Sur la détermination d'une relation par les types d'isomorphie de ses restrictions, C. R. Acad. Sci. Paris, Ser. A, Volume 275 (1972), pp. 951-953

[20] Lopez, G.; Rauzy, C. Reconstruction of binary relations from their restrictions of cardinality 2, 3, 4 and (n−1), I, Math. Logic Quart., Volume 38 (1992) no. 1, pp. 27-37

[21] Lopez, G.; Rauzy, C. Reconstruction of binary relations from their restrictions of cardinality 2, 3, 4 and (n−1), II, Math. Logic Quart., Volume 38 (1992) no. 1, pp. 157-168

Cité par Sources :