Isomorphie héréditaire et $ \{-4\}$-hypomorphie pour les tournois

Youssef Boudabbous

doi:10.1016/j.crma.2009.06.002

Logique/Combinatoire

Isomorphie héréditaire et

{- 4}

-hypomorphie pour les tournois
[Hereditary isomorphy and

{- 4}

-hypomorphy for tournaments]

Presented by: Jean-Yves Girard

Youssef Boudabbous ¹

¹Faculté des sciences de Sfax, BP 802, 3018 Sfax, Tunisie

Comptes Rendus. Mathématique, Volume 347 (2009) no. 15-16, pp. 841-844

Résumé (Original language)
Abstract

Étant donné un tournoi $T = (S, A)$ , pour toute partie X de S, le sous-tournoi de T induit par X est noté $T [X]$ . Nous montrons : Étant donnés deux tournois T et $T^{'}$ de même ensemble de sommets S à $n ⩾ 10$ éléments, si pour toute partie X à $n - 4$ éléments de S, les sous-tournois $T [X]$ et $T^{'} [X]$ sont isomorphes, alors pour toute partie Y de S, les sous-tournois $T [Y]$ et $T^{'} [Y]$ sont isomorphes. Il en découle un corollaire analogue pour les parties à $n - 5$ éléments.

Given a tournament $T = (V, A)$ , for every subset X of V the subtournament of T induced by X is denoted $T [X]$ . We prove: Given two tournaments T and $T^{'}$ on the same vertex set V with $n ⩾ 10$ elements, if for each subset X with $n - 4$ elements of V, the subtournaments $T [X]$ and $T^{'} [X]$ are isomorphic, then for every subset Y of V, the subtournaments $T [Y]$ and $T^{'} [Y]$ are isomorphic. An analogous corollary for the subsets with $n - 5$ elements is deduced.

Received: 2009-05-14
Accepted: 2009-05-23
Published online: 2009-07-02

DOI: 10.1016/j.crma.2009.06.002

Author's affiliations:

Youssef Boudabbous ¹

¹ Faculté des sciences de Sfax, BP 802, 3018 Sfax, Tunisie

@article{CRMATH_2009__347_15-16_841_0,
     author = {Youssef Boudabbous},
     title = {Isomorphie h\'er\'editaire et $ \{-4\}$-hypomorphie pour les tournois},
     journal = {Comptes Rendus. Math\'ematique},
     pages = {841--844},
     year = {2009},
     publisher = {Elsevier},
     volume = {347},
     number = {15-16},
     doi = {10.1016/j.crma.2009.06.002},
     language = {fr},
}

TY  - JOUR
AU  - Youssef Boudabbous
TI  - Isomorphie héréditaire et $ \{-4\}$-hypomorphie pour les tournois
JO  - Comptes Rendus. Mathématique
PY  - 2009
SP  - 841
EP  - 844
VL  - 347
IS  - 15-16
PB  - Elsevier
DO  - 10.1016/j.crma.2009.06.002
LA  - fr
ID  - CRMATH_2009__347_15-16_841_0
ER  -

%0 Journal Article
%A Youssef Boudabbous
%T Isomorphie héréditaire et $ \{-4\}$-hypomorphie pour les tournois
%J Comptes Rendus. Mathématique
%D 2009
%P 841-844
%V 347
%N 15-16
%I Elsevier
%R 10.1016/j.crma.2009.06.002
%G fr
%F CRMATH_2009__347_15-16_841_0

Youssef Boudabbous. Isomorphie héréditaire et $ \{-4\}$-hypomorphie pour les tournois. Comptes Rendus. Mathématique, Volume 347 (2009) no. 15-16, pp. 841-844. doi: 10.1016/j.crma.2009.06.002

References
Cited by

[1] J.A. Bondy A graph reconstructor's manual (O. Keendwell, ed.), Surveys in Combinatorics, London. Math. Soc. Lecture Note Ser., Cambridge Univ. Press, 1991, pp. 221-252

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

[3] M. Bouaziz; Y. Boudabbous La demi-isomorphie et les tournois fortement connexes finis, C. R. Acad. Sci. Paris, Sér. I, Volume 335 (2002), pp. 105-110

[4] H. Bouchaala; Y. Boudabbous La ${- k}$ -autodualité des sommes lexicographiques finies de tournois suivant un 3-cycle ou un tournoi critique, Ars Combin., Volume 81 (2006), pp. 33-64

[5] A. Boussaïri; P. Ille; G. Lopez; S. Thomassé The $C_{3}$ -structure of tournaments, Discrete Math., Volume 277 (2004), pp. 29-43

[6] R. Fraïssé, Abritement entre relations et spécialement entre chaînes, Symposi. Math. Instituto Nazionale di Alta Matematica 5, 1970, pp. 203–251

[7] T. Gallai Transitiv orientierbare Graphen, Acta Math. Acad. Sci. Hungar., Volume 18 (1967), pp. 25-66

[8] 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, Sér. A, Volume 274 (1972), pp. 1525-1528

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

[10] G. Lopez; C. Rauzy Reconstruction of binary relations from their restrictions of cardinality 2, 3, 4 and $(n - 1)$ , I, Z. Math. Logik Grundlag. Math., Volume 38 (1992), pp. 27-37

[11] G. Lopez; C. Rauzy Reconstruction of binary relations from their restrictions of cardinality 2, 3, 4 and $(n - 1)$ , II, Z. Math. Logik Grundlag. Math., Volume 38 (1992), pp. 157-168

[12] M. Pouzet Application d'une propriété combinatoire des parties d'un ensemble aux groupes et aux relations, Math. Z., Volume 150 (1976), pp. 117-134

[13] M. Pouzet Relations non reconstructibles par leurs restrictions, J. Combin. Theory B, Volume 1.26 (1979), pp. 22-34

[14] K.B. Reid; C. Thomassen Strongly self-complementary and hereditarily isomorphic tournaments, Monatsh. Math., Volume 81 (1976), pp. 291-304

Cited by Sources:

Comments - Policy