The {-3}-reconstruction and the {-3}-self duality of tournaments

Details The {-3}-reconstruction and the {-3}-self duality of tournaments The {-3}-reconstruction and the {-3}-self duality of tournaments

2012-04-11

arxiv.org/abs/1204.2513v1

Mathematics

Combinatorics

To appear in Ars Combinatoria; Published in Ars Combinatoria on April 2010

Scientific paper

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 \timesX)) 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 \ 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 \ I, (a,x) \in A if and only if (b,x) \in A. For instance, \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', on the set V, is {-k}-hypomorphic to T if for each set X on k vertices, T[V \ X] and T'[V \ 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 \ 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 [6] found by Y. Boudabbous and A. Boussairi.

Affiliated with

Also associated with

No associations

Rating

The {-3}-reconstruction and the {-3}-self duality of tournaments does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with The {-3}-reconstruction and the {-3}-self duality of tournaments, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The {-3}-reconstruction and the {-3}-self duality of tournaments will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-717219