|
|
Re: Degree sequences of tournaments
Posted:
Jan 31, 2012 10:17 PM
|
|
On Jan 31, 2:09 pm, taffer <djr...@bath.ac.uk> wrote:
> Any pair of tournaments of order n with outdegree sequence
If we're talking about tournaments I'd call it a score sequence.
> 0, 1, 2, ..., n-1 must be isomorphic to each other, right?
Sure.
> What other sequences have this property?
Beats me. Maybe you could find the answer in a book such as John W.
Moon's _Topics on Tournaments_. Meanwhile here is a partial answer.
Instead of trying to describe the *sequences* with that property, it
might be easier to describe the corresponding *tournaments*. I don't
know if there's a standard name for your property, so let's just say
that a tournament T is DSS (determined by its score sequence) if every
tournament with the same score sequence as T is isomorphic to T.
As you said, all transitive tournaments are DSS. More generally, a
tournament is DSS if and only if each of its strong components is DSS.
Thus, in order to find all DSS tournaments, it will suffice to find
all *strong* tournaments which are DSS. The only ones I know of ate
the tournaments of order 1, 3, 4, and 5 with respective score sequence
(0), (1, 1, 1), (1, 1, 2, 2), and (2, 2, 2, 2, 2).
E.g., the score sequence (1, 1, 1, 3, 5, 5, 6, 6, 10, 10, 10, 10, 10,
13) determines a unique tournament, up to isomorphism.
|
|
