The $\{-3\}$-Reconstruction and the $\{-3\}$-Self-Duality of Tournaments

Abstract

Let $T=(V,A)$ be a (finite) tournament and $k$ be a non-negative integer. For every subset $X$ of $V$\), the subtournament $T[X]=(X,A\cap (X\times X))$ of $T$, induced by $X$, is associated. The dual tournament of $T$, denoted by $T^{\ast }$, is the tournament obtained from $T$ by reversing all its arcs. The tournament $T$ is self-dual if it is isomorphic to its dual. $T$ is $(-k)$-self-dual if for each set $X$ of $k$ vertices, $T[V\setminus X]$ is self-dual. $T$ is strongly self-dual if each of its induced subtournaments is self-dual. A subset $I$ of $V$ is an interval of $T$ if for $a,b\in I$ and for $x\in V\setminus I$, $(a,x)\in A$ if and only if $(b,x)\in A$. For instance, $\mathrm{\varnothing }$, $V$, and $\{x\}$, where $x\in V$, are intervals of $T$ called trivial intervals. $T$ is indecomposable if all its intervals are trivial; otherwise, it is decomposable. A tournament $T^{\prime }$, on the set $V$, is $(-k)$-hypomorphic to $T$ if for each set $X$ on $k$ vertices, $T[V\setminus X]$ and $T^{\prime }[V\setminus X]$ are isomorphic. The tournament $T$ is $(-k)$-reconstructible if each tournament $(-k)$-hypomorphic to $T$ is isomorphic to it.

Suppose that $T$ is decomposable and $|V|\ge 9$. In this paper, we begin by proving the equivalence between the $(-3)$-self-duality and the strong self-duality of $T$. Then we characterize each tournament $(-3)$-hypomorphic to $T$. As a consequence of this characterization, we prove that if there is no interval $X$ of $T$ such that $T[X]$ is indecomposable and $|V\setminus X|\le 2$, then $T$ is $(-3)$-reconstructible. Finally, we conclude by reducing the $(-3)$-reconstruction problem.