MVLSC Home • Issue Contents

Recognizing Indecomposability for Tournaments
Rim Ben Hamadou, Imed Boudabbous and Nadia El Amri

A subset X of the vertex set V of a tournament T with arc set A is an interval of T provided that for any a, bX and xV \ X, (a, x) ∈ A if and only if (b, x) ∈ A. For example, ∅, the single-vertex sets and V are intervals of T, called trivial intervals. A tournament whose intervals are trivial is indecomposable; otherwise, it is decomposable. In this paper, we describe the pairs of tournaments T and T’  defined on the same vertex set V, such that T is indecomposable, T’  is decomposable and for each subset XV where | X |= 2, TX and T’ − X are both indecomposable or both decomposable.

Mathematical Subject Classification: 05C20, 05C60, 05C75.

Keywords: Digraph, tournament, interval, indecomposability, recognition.

Full Text (IP)