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, b ∈ X and x ∈ V \ 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 X ⊆ V where | X |= 2, T − X and T’ − X are both indecomposable or both decomposable.
Mathematical Subject Classification: 05C20, 05C60, 05C75.
Keywords: Digraph, tournament, interval, indecomposability, recognition.