Houmem BELKHECHINE, med IBOUDABBOUS, Kaouthar HZAMI

The prime tournaments T with |W5(T)|=|T |−2

We consider a tournament T = (V,A). For X ⊆ V , the subtournament of T induced by X is T[X] = (X,A ∩ (X ×X)). A module of T is a subset X of V such that for a,b ∈X and x ∈ V X, (a,x) ∈A if and only if (b,x) ∈ A. The trivial modules of T are ∅, {x}(x ∈ V), and V . A tournament is prime if all its modules are trivial. For n ≥ 2, W2n+1 denotes the unique prime tournament deﬁned on {0,...,2n} such that W2n+1[{0,...,2n−1}] is the usual total order. Given a prime tournament T , W5(T) denotes the set of v ∈ V such that there is W ⊆ V satisfying v ∈ W and T[W] is isomorphic to W5. B.J. Latka characterized the prime tournaments T such that W5(T) = ∅. The authors proved that if W5(T) ̸= ∅, then |W5(T)|≥|V | −2. In this article, we characterize the prime tournaments T such that |W5(T)|=|V | −2.

PDF

___

[1] Belkhechine H, Boudabbous I, Hzami K. Sous-tournois isomorphes `a W5 dans un tournoi ind´ecomposable. C R Acad Sci I Paris 2012; 350: 333337 (in French).
[2] Belkhechine H, Boudabbous I, Hzami K. Subtournaments isomorphic to W5 of an indecomposable tournament. J Korean Math Soc 2012; 49: 12591271.
[3] Belkhechine H, Boudabbous I, Hzami K. The indecomposable tournaments T with | W5(T)|=| T |−2. C R Acad Sci I Paris 2013; 351: 501504.
[4] Cournier A, Habib M. An eﬃcient algorithm to recognize prime undirected graphs. Lect Notes Comput Sci 1993; 657: 212224.
[5] Cournier A, Ille P. Minimal indecomposable graphs. Discrete Math 1998; 183: 6180.
[6] Dubey CK, Mehta SK, Deogun JS. Conditionally critical indecomposable graphs. Lect Notes Comput Sci 2005; 3595: 690700.
[7] Ehrenfeucht A, Rozenberg G. Primitivity is hereditary for 2-structures. Theor Comput Sci 1990; 70: 343358.
[8] Latka BJ. Structure theorem for tournaments omitting N5. J Graph Theor 2003; 42: 165192.
[9] Sayar MY. Partially critical indecomposable tournaments and partially critical supports. Contrib Discrete Math 2011; 6: 5276.
[10] Schmerl JH, Trotter WT. Critically indecomposable partially ordered sets, graphs, tournaments and other binary relational structures. Discrete Math 1993; 113: 191205.
[11] Spinrad J. P4-trees and substitution decomposition. Discrete Appl Math 1992; 39: 263291.