Houmem BELKHECHINE, İmed BOUDABBOUS, Kaouthar HZAMI

The prime tournaments $T$ with $\mid\! W_{5}(T) \!\mid = \mid\! T \!\mid -2$

We consider a tournament $T=(V, A)$. For $X\subseteq V$, the subtournament of $T$ induced by $X$ is $T[X] = (X, A \cap (X \times X))$. A module of $T$ is a subset $X$ of $V$ such that for $a, b\in X$ and $ x\in V\setminus X$, $(a,x)\in A$ if and only if $(b,x)\in A$. The trivial modules of $T$ are $\emptyset$, $\{x\}(x\in V)$, and $V$. A tournament is prime if all its modules are trivial. For $n\geq 2$, $W_{2n+1}$ denotes the unique prime tournament defined on $\{0,\dots,2n\}$ such that $W_{2n+1}[\{0,\dots,2n-1\}]$ is the usual total order. Given a prime tournament $T$, $W_{5}(T)$ denotes the set of $v\in V$ such that there is $W\subseteq V$ satisfying $v\in W$ and $T[W]$ is isomorphic to $W_{5}$. B.J. Latka characterized the prime tournaments $T$ such that $W_{5}(T)=\emptyset$. The authors proved that if $W_{5}(T)\neq \emptyset$, then $\mid\! W_{5}(T) \!\mid \geq \mid\! V \!\mid -2$. In this article, we characterize the prime tournaments $T$ such that $\mid\! W_{5}(T) \!\mid = \mid\! V \!\mid -2$.

Anahtar Kelimeler:

Tournament, prime, embedding, critical, partially critical

The prime tournaments $T$ with $\mid\! W_{5}(T) \!\mid = \mid\! T \!\mid -2$

Keywords:

Tournament, prime, embedding, critical, partially critical,

PDF

___

Belkhechine H, Boudabbous I, Hzami K. Subtournaments isomorphic to W5of an indecomposable tournament. J Korean Math Soc 2012; 49: 1259–1271.
Belkhechine H, Boudabbous I, Hzami K. The indecomposable tournaments T with| W5(T )|=| T | −2. C R Acad Sci I Paris 2013; 351: 501–504.
Cournier A, Habib M. An eﬃcient algorithm to recognize prime undirected graphs. Lect Notes Comput Sci 1993; 657: 212–224.
Cournier A, Ille P. Minimal indecomposable graphs. Discrete Math 1998; 183: 61–80.
Dubey CK, Mehta SK, Deogun JS. Conditionally critical indecomposable graphs. Lect Notes Comput Sci 2005; 3595: 690–700.
Ehrenfeucht A, Rozenberg G. Primitivity is hereditary for 2-structures. Theor Comput Sci 1990; 70: 343–358.
Latka BJ. Structure theorem for tournaments omitting N5. J Graph Theor 2003; 42: 165–192.
Sayar MY. Partially critical indecomposable tournaments and partially critical supports. Contrib Discrete Math 2011; 6: 52–76.
Schmerl JH, Trotter WT. Critically indecomposable partially ordered sets, graphs, tournaments and other binary relational structures. Discrete Math 1993; 113: 191–205.
Spinrad J. P4-trees and substitution decomposition. Discrete Appl Math 1992; 39: 263–291.