×

Bounds of Slater’s index of a tournament from its scores. (Encadrement de l’indice de Slater d’un tournoi à l’aide de ses scores.) (French) Zbl 0846.05040

Summary: We define a parameter \(\sigma(T)\) from the scores of a tournament \(T\). This parameter measures a remoteness between the tournament \(T\) and the transitive tournaments of the same order. Calling \(i(T)\) the minimum number of arcs to reverse to make \(T\) transitive, we show the relation \(\sigma(T)\leq i(T)\). Then we give bounds on the maximum value of \(i(T)\) for tournaments \(T\) with given value of \(\sigma\). Lastly, according to \(\sigma(T)\) and the number of vertices of \(T\), we deduce bounds of \(i(T)\) for any tournament \(T\).

MSC:

05C20 Directed graphs (digraphs), tournaments