A sequence of nonnegative integers s=(S1, s2, , sn) is a score sequence of an r-tournament if, for some positive integer r, ther is a directed graph with vertices v1, v2, , vn such that deg+(vj)=sj and deg-(vj)=r(n-1) -sj for each j=1, 2, , n. The score sequence problem of an r-tournament is: Given some positive integer r and a sequence of nonnegative integers, determine whether it is a score sequence of an r-tournament or not. In this paper, we consider several variations of the score sequence problem of an r-tournament, and give efficient algorithms.

Let G be any graph with property P (for example, general graph, directed graph, etc.) and S be nonnegative and non-decreasing integer sequence(s). The prescribed degree sequence problem is a problem to determine whether there is a graph G having S as the prescribed sequence(s) of degrees or outdegrees of the vertices. From 1950's, P has attracted wide attentions, and its many extensions have been considered. Let P be the property satisfying the following (1) and (2):(1) G is a directed graph with two disjoint vertex sets A and B. (2) There are r11 (r22, respectively) directed edges between every pair of vertices in A(B), and r12 directed edges between every pair of vertex in A and vertex in B. Then G is called an (r11, r12, r22)-tournament ("tournament", for short). The problem is called the score sequence pair problem of a "tournament" (realizable, for short). S is called a score sequence pair of a "tournament" if the answer of the problem is "yes." In this paper, we propose the characterizations of a score sequence pair of a "tournament" and an algorithm for determining in linear time whether a pair of two integer sequences is realizable or not.

A sequence of nonnegative integers S=(s1, s2, , sn) is graphical if there is a graph with vertices v1,v2, ,vn such that deg(vi)=si for each i=1, 2, , n. The graphical degree sequence problem is： Given a sequence of nonnegative integers, determine whether it is graphical or not. In this paper, we consider several variations of the graphical degree sequence problem and give efficient algorithms.