The C3-structure of the tournaments

✍ Scribed by Abderrahim Boussaı̈ri; Pierre Ille; Gérard Lopez; Stéphan Thomassé

• Publisher: Elsevier Science
• Year: 2004
• Tongue: English
• Weight: 282 KB
• Volume: 277
• Category: Article
• ISSN: 0012-365X
• DOI: 10.1016/s0012-365x(03)00244-9

✦ Synopsis

Let T = (V; E) be a tournament. The C3-structure of T is the family C3(T ) of the subsets {x; y; z} of V such that the subtournament T ({x; y; z}) is a cycle on three vertices. In another respect, a subset X of V is an interval of T provided that for a; b ∈ X and x ∈ V -X , (a; x) ∈ E if and only if (b; x) ∈ E. For example, ∅, {x}, where x ∈ V , and V are intervals of T , called trivial intervals. A tournament is indecomposable if all its intervals are trivial. Lastly, with each tournament T = (V; E) is associated the dual tournament T ? = (V; E ? ), deÿned as: for x; y ∈ V , (x; y) ∈ E ? if (y; x) ∈ E. The following theorem is proved. Given tournaments T = (V; E) and T = (V; E ) such that C3(T ) = C3(T ), if T is indecomposable, then T = T or T = T ? . In order to treat the nonindecomposable case, the interval inversion is introduced. The paper concludes with an extension of this result to the digraphs which do not admit as subdigraphs ({0; 1; 2}; {(0; 1); (1; 0); (1; 2)}) and ({0; 1; 2}; {(0; 1); (1; 0); (2; 1)}), and with a brief consideration of the inÿnite case.