Partially critical tournaments and partially critical supports

作者: Mohamed Y. Sayar

DOI: 10.11575/CDM.V6I1.62094

关键词:

摘要: Given a tournament $T=(V,A)$, with each subset $X$ of $V$ is associated the subtournament $T[X]=(X,A\cap (X\times X))$ $T$ induced by $X$. A $I$ is an interval $T$ provided that for any $a,b\in I$ and $x\in V\setminus I$, $(a,x)\in A$ if and only if $(b,x)\in A$. For example, $\emptyset$, $\{x\}$, where $x\in V$, are intervals called \emph{trivial}. A tournament indecomposable all its trivial; otherwise, it decomposable. Let $T=(V,A)$ be indecomposable tournament. The \emph{critical} every $x\in $T[V\setminus\{x\}]$ It is \emph{partially critical} there exists proper of $V$ such that $| X| \geq 3$, $T[X]$ indecomposable and every X$, is decomposable. partially critical tournaments are characterized. Lastly, given consider $X$ $|X|\geq 3$ indecomposable. The support according to family $x\in X$ and $T[V\setminus\{x,y\}]$ decomposable $y\in (V\setminus X)\setminus\{x\}$. It shown contains at most three vertices. whose supports contain least two vertices characterized.

参考文章(9)
Cournier Alain, Habib Michel, An Efficient Algorithm to Recognize Prime Undirected Graphs workshop on graph-theoretic concepts in computer science. pp. 212- 224 ,(1992) , 10.1007/3-540-56402-0_49
Jitender S. Deogun, Pierre Ille, Andrew Breiner, Partially critical indecomposable graphs Contributions to Discrete Mathematics. ,vol. 3, ,(2008) , 10.11575/CDM.V3I2.62003
A Ehrenfeucht, T Harju, G Rozenberg, The Theory of 2-Structures WORLD SCIENTIFIC. ,(1999) , 10.1142/4197
Jeremy Spinrad, P 4 -trees and substitution decomposition Discrete Applied Mathematics. ,vol. 39, pp. 263- 291 ,(1992) , 10.1016/0166-218X(92)90180-I
Mohamed Yahia Sayar, Les tournois partiellement critiques Comptes Rendus Mathematique. ,vol. 346, pp. 249- 252 ,(2008) , 10.1016/J.CRMA.2008.02.002
David P. Sumner, Graphs indecomposable with respect to the X-join Discrete Mathematics. ,vol. 6, pp. 281- 298 ,(1973) , 10.1016/0012-365X(73)90100-3
A. Ehrenfeucht, G. Rozenberg, Primitivity is hereditary for 2-structures Theoretical Computer Science. ,vol. 70, pp. 343- 358 ,(1990) , 10.1016/0304-3975(90)90131-Z
James H. Schmerl, William T. Trotter, Critically indecomposable partially ordered sets, graphs, tournaments and other binary relational structures Discrete Mathematics. ,vol. 113, pp. 191- 205 ,(1993) , 10.1016/0012-365X(93)90516-V
Pierre Ille, Indecomposable graphs Discrete Mathematics archive. ,vol. 173, pp. 71- ,(1997) , 10.1016/S0012-365X(96)00097-0