Les graphes 2-reconstructibles indécomposables

Abderrahim Boussaïri; Abdelhak Chaïchaâ

doi:10.1016/j.crma.2007.05.028

Logique/Combinatoire

Les graphes 2-reconstructibles indécomposables
[The 2-reconstructible indecomposable graphs]

Presented by: Jean-Yves Girard

Abderrahim Boussaïri ¹; Abdelhak Chaïchaâ ¹

¹ Université Hassan II, faculté des sciences Aïn-Chock, département de mathématiques et informatique, Km 8 route d'El Jadida, BP 5366 Maarif, Casablanca, Maroc

Comptes Rendus. Mathématique, Volume 345 (2007) no. 1, pp. 1-4.

Abstract
Résumé

A (direct) graph G is 2-reconstructible if any graph H obtained from G by reversing the orientation of some of its directed pairs, chosen arbitrarily, is isomorphic to G. Let G be a 2-reconstructible indecomposable graph, with r directed pairs. It follows from the results of Boussairi and Chaichaa (2003) that G has at least $2 r + 1$ vertices. In this Note, we determine, in terms of r, the minimum number of vertices of G.

Un graphe (orienté) G est 2-reconstructible si tout graphe H obtenu à partir de G en inversant l'orientation de certaines de ses paires orientées, choisies arbitrairement, est isomorphe à G. Soit G un graphe 2-reconstructible, indécomposable, ayant r paires orientées. Il découle des résultats obtenus dans Boussairi et Chaichaa (2003) que G possède au moins $2 r + 1$ sommets. Dans cette Note, nous déterminons, en fonction de r, le nombre minimum de sommets de G.

Received: 2007-05-07
Accepted: 2007-05-30
Published online: 2007-07-01

DOI: 10.1016/j.crma.2007.05.028

Author's affiliations:

Abderrahim Boussaïri ¹; Abdelhak Chaïchaâ ¹

¹ Université Hassan II, faculté des sciences Aïn-Chock, département de mathématiques et informatique, Km 8 route d'El Jadida, BP 5366 Maarif, Casablanca, Maroc

@article{CRMATH_2007__345_1_1_0,
     author = {Abderrahim Boussa{\"\i}ri and Abdelhak Cha{\"\i}cha\^a},
     title = {Les graphes 2-reconstructibles ind\'ecomposables},
     journal = {Comptes Rendus. Math\'ematique},
     pages = {1--4},
     publisher = {Elsevier},
     volume = {345},
     number = {1},
     year = {2007},
     doi = {10.1016/j.crma.2007.05.028},
     language = {fr},
}

TY  - JOUR
AU  - Abderrahim Boussaïri
AU  - Abdelhak Chaïchaâ
TI  - Les graphes 2-reconstructibles indécomposables
JO  - Comptes Rendus. Mathématique
PY  - 2007
SP  - 1
EP  - 4
VL  - 345
IS  - 1
PB  - Elsevier
DO  - 10.1016/j.crma.2007.05.028
LA  - fr
ID  - CRMATH_2007__345_1_1_0
ER  -

%0 Journal Article
%A Abderrahim Boussaïri
%A Abdelhak Chaïchaâ
%T Les graphes 2-reconstructibles indécomposables
%J Comptes Rendus. Mathématique
%D 2007
%P 1-4
%V 345
%N 1
%I Elsevier
%R 10.1016/j.crma.2007.05.028
%G fr
%F CRMATH_2007__345_1_1_0

Abderrahim Boussaïri; Abdelhak Chaïchaâ. Les graphes 2-reconstructibles indécomposables. Comptes Rendus. Mathématique, Volume 345 (2007) no. 1, pp. 1-4. doi : 10.1016/j.crma.2007.05.028. https://comptes-rendus.academie-sciences.fr/mathematique/articles/10.1016/j.crma.2007.05.028/

References
Cited by

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

[2] Y. Boudabbous; G. Lopez The minimal non- $(⩽ k)$ -reconstructible relations, Discrete Math., Volume 291 (2005) no. 1–3, pp. 19-40

[3] Y. Boudabbous, G. Lopez, Communication privée, 2002

[4] A. Boussairi; A. Chaichaa Sur les graphes 2-reconstructibles, C. R. Acad. Sci. Paris, Ser. I, Volume 337 (2003), pp. 437-440

[5] J.D. Dixon; B. Mortimer Permutation Groups, Springer, 1996

[6] G. Lopez L'indéformabilité des relations et multirelations binaires, Z. Logik Grundlag. Math., Volume 24 (1978), pp. 303-317

Cited by Sources:

Comments - Policy