Search All of the Math Forum:

Views expressed in these public forums are not endorsed by Drexel University or The Math Forum.

Topic: Degree sequences of tournaments
Replies: 3   Last Post: Feb 20, 2012 3:53 PM

 Search Thread: Advanced Search

 Messages: [ Previous | Next ]
 Butch Malahide Posts: 885 Registered: 6/29/05
Re: Degree sequences of tournaments
Posted: Jan 31, 2012 10:17 PM
 Plain Text Reply

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.

Date Subject Author
1/31/12 djrt20@bath.ac.uk
1/31/12 djrt20@bath.ac.uk
1/31/12 Butch Malahide
2/20/12 djrt20@bath.ac.uk

© Drexel University 1994-2013. All Rights Reserved.
The Math Forum is a research and educational enterprise of the Drexel University School of Education.