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 sommets. Dans cette Note, nous déterminons, en fonction de r, le nombre minimum de sommets de G.
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 vertices. In this Note, we determine, in terms of r, the minimum number of vertices of G.
Accepté le :
Publié le :
@article{CRMATH_2007__345_1_1_0,
author = {Boussa{\"\i}ri, Abderrahim and Cha{\"\i}cha\^a, Abdelhak},
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},
url = {http://www.numdam.org/articles/10.1016/j.crma.2007.05.028/}
}
TY - JOUR AU - Boussaïri, Abderrahim AU - Chaïchaâ, Abdelhak TI - Les graphes 2-reconstructibles indécomposables JO - Comptes Rendus. Mathématique PY - 2007 SP - 1 EP - 4 VL - 345 IS - 1 PB - Elsevier UR - http://www.numdam.org/articles/10.1016/j.crma.2007.05.028/ DO - 10.1016/j.crma.2007.05.028 LA - fr ID - CRMATH_2007__345_1_1_0 ER -
%0 Journal Article %A Boussaïri, Abderrahim %A Chaïchaâ, Abdelhak %T Les graphes 2-reconstructibles indécomposables %J Comptes Rendus. Mathématique %D 2007 %P 1-4 %V 345 %N 1 %I Elsevier %U http://www.numdam.org/articles/10.1016/j.crma.2007.05.028/ %R 10.1016/j.crma.2007.05.028 %G fr %F CRMATH_2007__345_1_1_0
Boussaïri, Abderrahim; Chaïchaâ, Abdelhak. Les graphes 2-reconstructibles indécomposables. Comptes Rendus. Mathématique, Tome 345 (2007) no. 1, pp. 1-4. doi : 10.1016/j.crma.2007.05.028. http://www.numdam.org/articles/10.1016/j.crma.2007.05.028/
[1] La 5-reconstructibilité et l'indécomposabilité des relations binaires, Eur. J. Combin., Volume 23 (2002), pp. 507-522
[2] The minimal non--reconstructible relations, Discrete Math., Volume 291 (2005) no. 1–3, pp. 19-40
[3] Y. Boudabbous, G. Lopez, Communication privée, 2002
[4] Sur les graphes 2-reconstructibles, C. R. Acad. Sci. Paris, Ser. I, Volume 337 (2003), pp. 437-440
[5] Permutation Groups, Springer, 1996
[6] L'indéformabilité des relations et multirelations binaires, Z. Logik Grundlag. Math., Volume 24 (1978), pp. 303-317
Cité par Sources :
