The $ (⩽6)$-half-reconstructibility of digraphs

Dammak, Jamel; Salem, Baraa

doi:10.1016/j.crma.2014.03.009

Combinatorics

The

(⩽ 6)

-half-reconstructibility of digraphs
[La

(⩽ 6)

-demi-reconstructibilité des graphes orientés]

Présenté par : the Editorial Board

Dammak, Jamel ¹ ; Salem, Baraa ¹

¹ 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.

Résumé
Abstract

Soit $G = (V, A)$ un graphe orienté. À toute partie X de V, on associe le sous-graphe orienté $G [X] = (X, A \cap (X \times 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 \in {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 \cap (X \times 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 \in {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 : 2011-01-29
Accepté le : 2014-03-10
Publié le : 2014-06-19

DOI : 10.1016/j.crma.2014.03.009

Affiliations des auteurs :

Dammak, Jamel ¹ ; Salem, Baraa ¹

¹ 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 = {http://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  - http://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 http://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. http://www.numdam.org/articles/10.1016/j.crma.2014.03.009/

Bibliographie
Cité par

[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 :