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

Jamel Dammak; Baraa Salem

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

Jamel Dammak ¹ ; Baraa Salem ¹

¹ Département de Mathématiques, Faculté des Sciences de Sfax, BP 802, 3018 Sfax, Tunisia

Comptes Rendus. Mathématique, Volume 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 :

Jamel Dammak ¹ ; Baraa Salem ¹

¹ Département de Mathématiques, Faculté des Sciences de Sfax, BP 802, 3018 Sfax, Tunisia

@article{CRMATH_2014__352_7-8_541_0,
     author = {Jamel Dammak and Baraa Salem},
     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},
}

TY  - JOUR
AU  - Jamel Dammak
AU  - Baraa Salem
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
DO  - 10.1016/j.crma.2014.03.009
LA  - en
ID  - CRMATH_2014__352_7-8_541_0
ER  -

%0 Journal Article
%A Jamel Dammak
%A Baraa Salem
%T The $ (⩽6)$-half-reconstructibility of digraphs
%J Comptes Rendus. Mathématique
%D 2014
%P 541-545
%V 352
%N 7-8
%I Elsevier
%R 10.1016/j.crma.2014.03.009
%G en
%F CRMATH_2014__352_7-8_541_0

Jamel Dammak; Baraa Salem. The $ (⩽6)$-half-reconstructibility of digraphs. Comptes Rendus. Mathématique, Volume 352 (2014) no. 7-8, pp. 541-545. doi : 10.1016/j.crma.2014.03.009. https://comptes-rendus.academie-sciences.fr/mathematique/articles/10.1016/j.crma.2014.03.009/

Bibliographie
Cité par

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

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

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

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

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

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

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

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

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

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

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

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

[13] J. Dammak 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] R. Fraïssé Abritement entre relations et spécialement entre chaînes, INDAM, Rome, 1969/70, Academic Press, London (1971), pp. 203-251

[16] 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

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

[18] 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, Ser. A, Volume 274 (1972), pp. 1525-1528

[19] G. Lopez 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] G. Lopez; C. Rauzy 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] G. Lopez; C. Rauzy 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 :

Commentaires - Politique

Ces articles pourraient vous intéresser

${- 1}$ -self dual finite prechains and applications

Houcine Bouchaala; Youssef Boudabbous; Gérard Lopez

C. R. Math (2013)

Les paires de tournois ${- 3}$ -hypomorphes

Mouna Achour; Youssef Boudabbous; Abderrahim Boussaïri

C. R. Math (2012)

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

Nadia El Amri

C. R. Math (2008)