Sur la répartition des diamants dans un tournoi |
| |
Authors: | Houcine Bouchaala |
| |
Affiliation: | Université de Sfax, Institut préparatoire aux études d''ingénieurs de Sfax, département de la préparation mathématiques-physique, BP 805, 3000 Sfax, Tunisie |
| |
Abstract: | A tournament T=(V,A) is a directed graph such that for every x,y∈V, where x≠y, (x,y)∈A if and only if (y,x)?A. For example, the 3-cycle is the tournament ({1,2,3}, {(1,2),(2,3),(3,1)}). Up to an isomorphism, there are two tournaments with 4 vertices and containing an unique 3-cycle which we call diamonds. We prove that for any tournament T defined on n?9 vertices, either T contains at least 2n?6 diamonds or the number of diamonds contained in T is equal to 0, n?3 or 2n?8. Following the characterization of the tournaments without diamonds due to Gnanvo and Ille (Z. Math. Logik Grundlag. Math. 38 (1992) 283–291) and to Lopez and Rauzy (Z. Math. Logik Grundlag. Math. 38 (1992) 27–37), we study the morphology of the tournaments defined on n?5 vertices and which contain exactly n?3 or 2n?8 diamonds. To cite this article: H. Bouchaala, C. R. Acad. Sci. Paris, Ser. I 338 (2004). |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|