Indecomposable tournaments with minimum Slater index

Read full text
Authors: Houmem Belkhechine, Cherifa Ben Salha, Rim Romdhane
Cited by: 0
References: 31

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