Construction of an (r11, r12, r22)-Tournament from a Score Sequence Pair

Let G be any directed graph 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 with S as the prescribed sequence(s) of outdegrees of the vertices. Let G be the property satisfying the following (1) and (2): (1) G has two disjoint vertex sets A and B; (2) For every vertex pair u, v isin G (u ne v), (G satisfies |{uv}| + |{vu}|) = {( (r11 if u, v isin A) (r12 if u isin A, v isin B) (r22 if u, v isin B)), where uv (vu, respectively) means a directed edges from u to v (from v to u). Then G is called an (r11, r12, r22)-tournament ("tournament", for short). When G is a "tournament", the prescribed degree sequence problem is called the score sequence pair problem of a "tournament", and S is called a score sequence pair of a "tournament" (or S is realizable) if the answer is "yes". We proposed the characterizations of a "tournament" and an algorithm for determining in linear time whether a pair of two integer sequences is realizable or not (Takahashi et al., 2006). In this paper, we propose an algorithm for constructing a "tournament" from such a score sequence pair.