Demi-isomorphie, autodualité et tournois non fortement connexes finis
Comptes Rendus. Mathématique, Tome 335 (2002) no. 5, pp. 411-416.

Soient T=(S,A) un tournoi fini à n sommets et F un ensemble d'entiers positifs ⩽n. Le dual de T est le tournoi T * =(S,A * ) défini par : pour tous x,yS, (y,x)A * si et seulement si (x,y)∈A. A chaque partie X de S est associé le sous-tournoi T(X)=(X,A∩(X×X)) de T induit par X. Le tournoi T est fortement connexe si pour tous x,yS, avec xy, il existe une suite x0=x,…,xp=y telle que pour i∈{0,…,p−1}, (xi,xi+1)∈A. Un demi-isomorphisme de T sur un tournoi T′ est soit un isomorphisme de T sur T′ soit un isomorphisme de T * sur T′. Un tournoi T′, ayant le même ensemble de sommets S que T, est F-demi-isomorphe à T lorsque pour toute partie X de S telle que |X|∈F, les sous-tournois T(X) et T′(X) sont demi-isomorphes. Nous étudions la {3,n−2}-demi-isomorphie et la {n−3}-demi-isomorphie entre deux tournois à n sommets dont l'un est non fortement connexe.

Let T=(V,A) be a finite tournament with n vertices and let F be a set of non negative integers ⩽n. The dual of T is the tournament T * =(V,A * ) defined by: for all x,yV, (y,x)A * if and only if (x,y)∈A. To every subset X of V is associated the subtournament T(X)=(X,A∩(X×X)) of T induced by X. The tournament T is strongly connected if for all x, yV, with xy, there is a sequence x0=x,…,xp=y such that for i∈{0,…,p−1}, (xi,xi+1)∈A. An half-isomorphism from T onto a tournament T′ is either an isomorphism from T onto T′ or an isomorphism from T * onto T′. A tournament T′, with the same set of vertices V than T, is F-half-isomorphic to T if for every subset X of V such that |X|∈F, the subtournaments T(X) and T′(X) are half-isomorphic. We study the {3,n−2}-half-isomorphy and the {n−3}-half-isomorphy between two tournaments with n vertices, one of which is non strongly connected.

Reçu le :
Accepté le :
Publié le :
DOI : 10.1016/S1631-073X(02)02498-6
Bouaziz, Moncef 1 ; Boudabbous, Youssef 2

1 Faculté des sciences de Tunis, département de mathématiques, Elmanar II 2092, Tunisie
2 Al-Jouf Technical College, P.O. Box 1642, Sakaka, Al-Jouf, Saudi Arabia
@article{CRMATH_2002__335_5_411_0,
     author = {Bouaziz, Moncef and Boudabbous, Youssef},
     title = {Demi-isomorphie, autodualit\'e et tournois non fortement connexes finis},
     journal = {Comptes Rendus. Math\'ematique},
     pages = {411--416},
     publisher = {Elsevier},
     volume = {335},
     number = {5},
     year = {2002},
     doi = {10.1016/S1631-073X(02)02498-6},
     language = {fr},
     url = {http://www.numdam.org/articles/10.1016/S1631-073X(02)02498-6/}
}
TY  - JOUR
AU  - Bouaziz, Moncef
AU  - Boudabbous, Youssef
TI  - Demi-isomorphie, autodualité et tournois non fortement connexes finis
JO  - Comptes Rendus. Mathématique
PY  - 2002
SP  - 411
EP  - 416
VL  - 335
IS  - 5
PB  - Elsevier
UR  - http://www.numdam.org/articles/10.1016/S1631-073X(02)02498-6/
DO  - 10.1016/S1631-073X(02)02498-6
LA  - fr
ID  - CRMATH_2002__335_5_411_0
ER  - 
%0 Journal Article
%A Bouaziz, Moncef
%A Boudabbous, Youssef
%T Demi-isomorphie, autodualité et tournois non fortement connexes finis
%J Comptes Rendus. Mathématique
%D 2002
%P 411-416
%V 335
%N 5
%I Elsevier
%U http://www.numdam.org/articles/10.1016/S1631-073X(02)02498-6/
%R 10.1016/S1631-073X(02)02498-6
%G fr
%F CRMATH_2002__335_5_411_0
Bouaziz, Moncef; Boudabbous, Youssef. Demi-isomorphie, autodualité et tournois non fortement connexes finis. Comptes Rendus. Mathématique, Tome 335 (2002) no. 5, pp. 411-416. doi : 10.1016/S1631-073X(02)02498-6. http://www.numdam.org/articles/10.1016/S1631-073X(02)02498-6/

[1] M. Bouaziz, Y. Boudabbous, La demi-isomorphie et les tournois fortement connexes finis, à paraître aux C. R. Acad. Sci. Paris

[2] Boudabbous, Y.; Dammak, J. Sur la (−k)-demi-reconstructibilité des tournois finis, C. R. Acad. Sci. Paris, Série I, Volume 326 (1998), pp. 1037-1040

[3] Boudabbous, Y.; Dammak, J.; Ille, P. Indecomposability and duality of tournaments, Discrete Math., Volume 223 (2000), pp. 55-82

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

[5] Hagendorf, J.G.; Lopez, G. La demi-reconstructibilité des relations binaires d'au moins 13 éléments, C. R. Acad. Sci. Paris, Série I, Volume 317 (1993), pp. 7-12

[6] Ille, P. La reconstruction des relations binaires, C. R. Acad. Sci. Paris, Série I, Volume 306 (1988), pp. 635-638

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

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

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

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

Cité par Sources :