Indecomposable tournaments with minimum Slater index
Abstract
The Slater index (resp.decomposability index) of a tournament is the minimum number of arcs that must be reversed in that tournament in order to make it a total order (resp.indecomposable (under modular decomposition)).The first author [H.Belkhechine, Decomposability index of tournaments, Discrete Math.340 (2017) 2986-2994] showed that for every integer n ≥ 5, the decomposability index of the n-vertex total order equals ⌈ n+1 4 ⌉.It follows that the Slater index of an indecomposable n-vertex tournament is at least ⌈ n+1 4 ⌉.This led A. Boussaïri to ask the following question during the thesis defense of the second author on July 2, 2021: what are the indecomposable tournaments T whose Slater index is minimum over all indecomposable tournaments with the same vertex set as T ?These tournaments are then the indecomposable tournaments T obtained from a total order by reversing exactly ⌈ v(T )+1 4 ⌉ arcs, where v(T ) is the number of vertices of T .In this paper, we characterize such tournaments by means of so-called irreducible pairings.
Fields of Study & Subjects
Advanced Graph Theory Research
Advanced Combinatorial Mathematics
Complexity and Algorithms in Graphs
Publication details
- Journal / source
- Advances in Pure and Applied Mathematics
- Volume
- 17
- Issue
- 1
- Pages
- 60–77
- Publication date
- 1 January 2026
- Language
- FR