Nombre maximum d’ordres de Slater des tournois $T$ vérifiant $\sigma \left(T\right)=1$

Hudry, Olivier 

Mathématiques informatique et sciences humaines, Tome 140 (1997), pp. 51-58

Résumé (VO)

On s’intéresse ici au nombre maximum d’ordres de Slater qu’admettent les tournois $T$ vérifiant $\sigma \left(T\right)=1$, où $\sigma \left(T\right)$ est un paramètre calculé à partir des scores de $T$. On détermine ce nombre maximum d’ordres de Slater, de l’ordre de $2^{n/2}$, si $n$ désigne le nombre de sommets. On donne de plus la forme des tournois $T$ vérifiant $\sigma \left(T\right)=1$ et maximisant le nombre d’ordres de Slater. En particulier, on obtient que ces tournois ne sont pas fortement connexes pour $n$ pair.

Abstract

We consider here the maximum number of Slater orders that a tournament $T$ with $\sigma \left(T\right)=1$ can get, where $\sigma \left(T\right)$ is a parameter defined from the scores of $T$. We compute this maximum number, which is about $2^{n/2}$, if $n$ denotes the number of vertices. We depict also the tournaments $T$ with $\sigma \left(T\right)=1$ maximizing the number of Slater orders and we show that these tournaments are not strongly connected for $n$ even.