×

The \(\{-3\}\)-reconstruction and the \(\{-3\}\)-self duality of tournaments. (English) Zbl 1363.05183

Summary: Let \(T=(V,A)\) be a (finite) tournament and \(k\) be a non negative integer. For every subset \(X\) of \(V\) is associated the subtournament \(T[X]=(X, A\cap (X\times X))\) of \(T\), induced by \(X\). 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, \(\emptyset \), \(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| \geq 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| \leq 2\), then \(T\) is \(\{-3\}\)-reconstructible. Finally, we conclude by reducing the \(\{-3\}\)-reconstruction problem to the indecomposable case (between a tournament and its dual). In particular, we find and improve, in a less complicated way, the results of Y. Boudabbous and A. Boussaïri [C. R. Acad. Sci., Paris, Sér. I 320, No. 4, 397–400 (1995; Zbl 0831.04001)].

MSC:

05C60 Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.)
05C20 Directed graphs (digraphs), tournaments

Citations:

Zbl 0831.04001
PDFBibTeX XMLCite
Full Text: arXiv