Partially critical tournaments and partially critical supports

  • Mohamed Y. Sayar

Abstract

Given a tournament $T=(V,A)$, with each subset $X$ of $V$ is associated the subtournament $T[X]=(X,A\cap (X\times X))$ of $T$ induced by $X$. A subset $I$ of $V$ is an interval of $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$, and $V$ are intervals of $T$ called \emph{trivial}. A tournament is indecomposable if all its intervals are trivial; otherwise, it is decomposable. Let $T=(V,A)$ be an indecomposable tournament. The tournament $T$ is \emph{critical} if for every $x\in V$, $T[V\setminus\{x\}]$ is decomposable. It is \emph{partially critical} if there exists a proper subset $X$ of $V$ such that $| X| \geq 3$, $T[X]$ is indecomposable and for every $x\in V\setminus X$, $T[V\setminus\{x\}]$ is decomposable. The partially critical tournaments are characterized. Lastly, given an indecomposable tournament $T=(V,A)$, consider a proper subset $X$ of $V$ such that $|X|\geq 3$ and $T[X]$ is indecomposable. The partially critical support of $T$ according to $T[X]$ is the family of $x\in V\setminus X$ such that $T[V\setminus\{x\}]$ is indecomposable and $T[V\setminus\{x,y\}]$ is decomposable for every $y\in (V\setminus X)\setminus\{x\}$. It is shown that the partially critical support contains at most three vertices. The indecomposable tournaments whose partially critical supports contain at least two vertices are characterized.
Published
2011-04-04
Section
Articles