Demi-isomorphie, autodualité et tournois non fortement connexes finis

Bouaziz, Moncef¹ ; Boudabbous, Youssef²

¹ Faculté des sciences de Tunis, département de mathématiques, Elmanar II 2092, Tunisie
² Al-Jouf Technical College, P.O. Box 1642, Sakaka, Al-Jouf, Saudi Arabia

Comptes Rendus. Mathématique, Tome 335 (2002) no. 5, pp. 411-416

Résumé (VO)

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^{*}=(\mathrm{S},{\mathrm{A}}^{*})$ défini par : pour tous x,y∈S, $(\mathrm{y},\mathrm{x})\in {\mathrm{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,y∈S, avec x≠y, il existe une suite x₀=x,…,x_p=y telle que pour i∈{0,…,p−1}, (x_i,x_i+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.

Abstract

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^{*}=(\mathrm{V},{\mathrm{A}}^{*})$ defined by: for all x,y∈V, $(\mathrm{y},\mathrm{x})\in {\mathrm{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, y∈V, with x≠y, there is a sequence x₀=x,…,x_p=y such that for i∈{0,…,p−1}, (x_i,x_i+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.

Détail

Reçu le : 2002-06-26
Accepté le : 2002-07-09
Publié le : 2002-01-01

DOI : 10.1016/S1631-073X(02)02498-6