Alley CATs in search of good homes

Frank Ruskey ^{∗}

Department of Computer Science University of Victoria Victoria, B.C., V8W 3P6, Canada

Robert Cohen and Peter Eades and Aaron Scott

Department of Computer Science The University of Newcastle Newcastle, NSW, Australia

Abstract

A score sequence of a tournament is a monotonically non-decreasing sequence of the out-degrees of its vertices. We develop two algorithms that generates all score sequences, each of which appears to use only a constant amount of computation per sequence produced.

A degree sequence of a graph is a monotonically non-increasing sequence of the degrees of its vertices. We develop an algorithm that generates all degree sequences of given length and observe that the algorithm does only constant computation per sequence produced. This algorithm is extended to generate degree sequences of connected graphs, and of biconnected graphs.

1 Introduction

There is considerable interest in the Mathematical community in the sequence of degrees of vertices of directed and undirected graphs. Indeed, a search of the MathSci Index reveals well over 200 references which contain “degree sequence” in the title or abstract. We consider here the question of efficiently generating these sequences.

When generating combinatorial sequences a desirable goal is that the running time of the algorithm be proportional to the number of sequences produced. Such algorithms are said to be CAT, meaning that they run in \underline{C}onstant \underline{A}mortized \underline{T}ime. For the purposes of this paper we regard an algorithm as being an alley CAT if its experimental behavior is observed to be CAT, but that no proof of CAT behavior has been found. Once a proof has been given the algorithm has found a good home and is no longer an alley CAT. In this paper we present simple alley CATs for generating degree sequences of graphs and score sequence of tournaments.

∗Research supported by NSERC grant A3379.

2 Score Sequences

A tournament is a directed graph G = (V, E) in which, for every pair u, v ∈ V, either (u, v) ∈ E or (v, u) ∈ E, but not both. In other words, it is a complete graph in which every edge has been given an orientation. A score sequence of a tournament is a monotonically non-decreasing sequence of the out-degrees of its vertices. For example, any transitive tournament on n vertices has score sequence (0, 1, …, n − 1).

Algorithms for generating score sequences are given in the papers of Narayana, Mathsen, and Sarangi [11] and Gervacio [6]. Neither of these algorithms runs in constant amortized time nor are these as conceptually simple as the algorithm we present below.

There is a simple characterization of score sequences due to Landau [9].

Theorem 1 (Landau) A sequence s_{1} ≤ s_{2} ≤ ⋯ ≤ s_{n} of integers is a score sequence of a tournament if and only if

∑_{i=1}^{k} s_{i} ≥ \binom{k}{2}  (1)

for k = 1, 2, …, n with equality holding for k = n.

The previous theorem suggests that it may be possible to characterize those sequences that are prefixes of score sequences of some given length. Define a n-prescore sequence to be any prefix of some score sequence of length n. For example, 122 is a 5-prescore sequence but is not a 4-prescore sequence. Note that we wrote 122 for (1, 2, 2) above; we will drop the use of commas and parentheses in our examples when no confusion can arise. Our algorithm is based on the following theorem, which follows easily from the previous theorem.

Theorem 2 If s_{1}, s_{2}, …, s_{k−1} is a n-prescore sequence then s_{1}, s_{2}, …, s_{k−1}, s_{k} is a n-prescore sequence if and only if

max(s_{k−1}, \binom{k}{2} − p_{k}) ≤ s_{k} ≤ ⌊\frac{\binom{n}{2} − p_{k}}{n − k + 1}⌋ ,

where p_{k} = s_{1} + s_{2} + ⋯ + s_{k−1}, and s_{0} = 0.

This theorem leads immediately to the simple algorithm shown in Figure 1.

The initial call is gen(1,0) and C[k] is the binomial coefficient \binom{k}{2} = k(k − 1)/2. Parameter sum is the same as the value p_{k}. The call PrintIt( sum ) sets s[n] to C[n]-sum, and does whatever processing of the score sequence is desired.

Since only a constant amount of computation is done for each recursive call and every recursive call produces at least one score sequence, the amount of computation used by the algorithm is proportional to the number of nodes in the underlying computation tree.

Unfortunately, it seems difficult to determine the size of this tree since even determining the asymptotic number of leaves requires considerable effort. Let s(n) denote

procedure gen ( k, sum : integer );
var i : integer;
begin
  if k = n then PrintIt( sum )
  else begin
     for i := max(s[k-1],C[k]-sum) to (C[n]-sum) div (n-k+1) do begin
        s[k] := i;  gen( k+1, sum+i );
     end;
  end;
end {of gen};

Figure 1: Pascal code for generating score sequences.

the number of score sequences of length n. Winston and Kleitman [18] show that there are constants c_{1} and c_{2} such that

c_{1} \frac{4^{n}}{n^{5/2}} < s(n) < c_{2} \frac{4^{n}}{n^{2}} ,

but the exact asymptotic value of s(n) is unknown, although they conjecture that s(n) = Θ(4^{n}/n^{5/2}). It seems plausible that their methods could be used to bound the size of the computation tree.

Nevertheless, Table 2 shows that the ratio of recursive calls to number of leaves is monotonically decreasing (for n > 5) to some limit less than three, and so the algorithm is an alley CAT.

2.1 Another approach

The approach of the previous section might be called the “increasing sequence approach”. Another approach, the “integer partition approach”, has been suggested by Carla Savage [14]. Define P_{n}(p, k) to be the set of all sequences s_{1} ≤ s_{2} ≤ ⋯ ≤ s_{n} that satisfy (1) and such that ∑_{i=1}^{n} s_{i} = p and s_{n} ≤ k. The number of score sequences of length n is P_{n}(\binom{n}{2}, n − 1), where P_{n}(p, k) = |P(n, k)|. We are led to the following recurrence relation, which has no zero terms (and therefore can be turned into a recursive algorithm where every call produces at least one score sequence).

P_{n}(p, k) = \{ \begin{matrix}1 & if n = 1, k ≥ p \\ P_{n−1}(p − k, k) & if k − 1 < p/n \\ P_{n}(p, k − 1) & if p − k < \binom{n−1}{2} \\ P_{n−1}(p − k, k) + P_{n}(p, k − 1) & otherwise. \end{matrix}

The progam that arises from this recurrence relation is shown in Figure 2. It is also an alley CAT, but the size of its computation tree is about twice as large as the computation tree of the original algorithm of Figure 1.

n  1-nodes  calls  s(n) calls / s(n)
1  1  1  1 1.000000
2  2  2  1 2.000000
3  4  5  2 2.500000
4  7  10  4 2.500000
5  18  25  9 2.777777
6  42  60  22 2.727272
7  113  161  59 2.728813
8  311  445  167 2.664670
9  895  1283  490 2.618367
10  2657  3817  1486 2.568640
11  8139  11702  4639 2.522526
12  25522  36721  14805 2.480310
13  81599  117493  48107 2.442326
14  265493  382484  158808 2.408468
15  876985 1263896  531469 2.378118
16 2934862 4230834 1799659 2.350908
17 9934666 14324411 6157068 2.326498
18 33972892 48990040 21258104 2.304534
19 117229853 169058807 73996100 2.284698
20 407804236 588104519 259451116 2.266725

Table 1: The number of recursive calls from gen(n).

procedure gen ( n,p,k : integer );
begin
if n = 1 then begin  a[1] := p;  PrintIt  end
else begin
if k-1 >= ceiling( p,n ) then gen( n, p, k-1 );
if p-k >= C[n-1] then begin
a[n] := k;  gen( n-1, p-k, k );
end;
end;
end {of gen};

Figure 2: Another algorithm for generating score sequences.

3 Degree Sequences

Degree sequences have been characterized and several papers written about building graphs with given degree sequence, but, suprisingly, there seem to be no published algorithms for generating degree sequences. Our aim in this paper is to develop an efficient algorithm for generating all degree sequences. Our algorithm can be thought of as an instance of “reverse search”, a term originated by Avis and Fukuda [2]. That is to say, we impose a rooted tree structure on the set of degree sequences by noting how to obtain the parent of a node, inverting the relationship to obtain the children of a node, and finally implementing an algorithm based on this inversion.

A sequence D = (d_{1}, d_{2}, …, d_{n}) is said to be graphical if there is a graph on vertex set [n] such that vertex i has degree d_{i}. If in addition d_{1} ≥ d_{2} ≥ ⋯ ≥ d_{n} then D is a degree sequence. Define D_{n} to be the set of all degree sequences of length n.

There are two simple characterization of degree sequences. The oldest, due to Havel [8] and Hakimi [7] turns out to be most useful for our purposes. Another characterization, due to Erdös and Gallai [4], one the surface appears similar to the Landau characterization of score sequences, but unfortunately does not seem to lend itself to a characterization of prefixes of degree sequences.

Theorem 3 (Erdös-Gallai) Let D = (d_{1}, d_{2}, …, d_{n}) be a sequence of integers with n > d_{1} ≥ d_{2} ≥ ⋯ ≥ d_{n} ≥ 0. Then D is a degree sequence if and only if, for i = 1, 2, …, n,

∑_{j=1}^{i} d_{i} ≤ i(i − 1) + ∑_{j=i+1}^{n} min{i, d_{j}}.

Theorem 4 (Havel-Hakimi) A sequence d_{1} ≥ d_{2} ≥ ⋯ ≥ d_{n} of integers is the degree sequence of some graph if and only if c_{1}, c_{2}, …, c_{n−1} is graphical, where

c_{i} = \{ \begin{matrix}d_{i+1} − 1 & if 1 ≤ i ≤ d_{1} \\ d_{i+1} & if d_{1} + 1 ≤ i ≤ n − 1 \end{matrix}

Let S_{n} be the set of all sequences D = (d_{1}, d_{2}, …, d_{n}) for which n − 1 ≥ d_{1} ≥ d_{2} ≥ ⋯ ≥ d_{n} ≥ 0. Define a function f_{n} : S_{n} → S_{n−1} as follows. First, let h = d_{n}, p = max{j | d_{j} > d_{h}}, and q = min{j | j ≤ n and d_{j} < d_{h}}. Given D ∈ S_{n}, define C = (c_{1}, c_{2}, …, c_{n−1}) = f_{n}(D) as follows.

c_{i} = \{ \begin{matrix}d_{i} − 1 & if 1 ≤ i ≤ p or p + q − h ≤ i ≤ q − 1, \\ d_{i} & if p + 1 ≤ i ≤ p + q − h − 1 or q ≤ i ≤ n − 1. \end{matrix}

The subscript n in f_{n} will be dropped when no ambiguity can arise. We call f(D) the reduction of D. Our algorithm is based on the following variant of Theorem 4 (from Takahashi, Imai and Asano [16]).

Corollary 1 For n > 0 and D ∈ S_{n}, the sequence D ∈ D_{n} if and only if f_{n}(D) ∈ D_{n−1}.

Note that f imposes an infinite tree structure on the set of all degree sequences. The root of the tree is the single degree sequence 0 of a graph with one vertex. Otherwise, degree sequence D has parent f(D). Level n (with the root at level 1) in this tree consists of all degree sequences of length n.

In the theorem above let f denote the function that maps D to C; i.e., f(D) = C. This theorem implies that there is a tree structure of degree sequences where f(D) = C is the parent of D. Of course, C will, in general, have children other than D. The root of the tree is the single element sequence (0). Theorem 1 tells us the parent of a node; to develop a generation algorithm we need to know all children of a node, that is, we wish to know the set f^{−1}(C). A careful examination of Theorem 1 reveals the following characterization.

Theorem 5 Let C ∈ D_{n−1}. The sequence D ∈ f^{−1}(C) if and only if one of the four mutually exclusive conditions given below are met. Let h denote d_{n}, p = max{i | c_{i} > c_{h} or i = 0}, and q = min{j | c_{j} < c_{h} or j = n}.

[Case 1a: h = c_{n−1} + 1 and c_{h} = h and p + n − q ≤ h.]

d_{i} = \{ \begin{matrix}c_{i} + 1 & if 1 ≤ i ≤ h − n + q or q ≤ i ≤ h \\ c_{i} & if h − n + q + 1 ≤ i ≤ q − 1 \end{matrix}

[Case 1b: h = c_{n−1} + 1 and c_{h} = h − 1 and s + n − p − 1 ≤ h, where s = max{i | c_{i} > h}.]

d_{i} = \{ \begin{matrix}c_{i} + 1 & if 1 ≤ i ≤ h − n + p + 1 or p + 1 ≤ i ≤ n − 1 \\ c_{i} & if h − n + p + 2 ≤ i ≤ p \end{matrix}

[Case 2a: 0 ≤ h ≤ c_{n−1} and there are a, b such that a ≤ b, a + b = h + q, a > p, b < n, and c_{b} = c_{h} − 1]

d_{i} = \{ \begin{matrix}c_{i} + 1 & if 1 ≤ i ≤ a − 1 or q ≤ i ≤ b \\ c_{i} & if a ≤ i ≤ q − 1 or b ≤ i ≤ n − 1 \end{matrix}

[Case 2b: 0 ≤ h ≤ c_{n−1} and there are a, b such that a < b, a + b = p + h + 1, j < q, and c_{a} = c_{h} + 1]

d_{i} = \{ \begin{matrix}c_{i} + 1 & if 1 ≤ i ≤ a − 1 or p + 1 ≤ i ≤ b \\ c_{i} & if a ≤ i ≤ p or b + 1 ≤ i ≤ n − 1 \end{matrix}

The following examples illustrate the four cases.

• [Case 1a:] f(7744444) = 664433 or f(77766666666) = 6666666555.

• [Case 1b:] f(333333) = 33222.

• [Case 2a:] f^{−1}(87776665555) ⊇ {988876655555, 988777655555, 987777755555}.

• [Case 2b:] f^{−1}(86666665555) ⊇ {977766665555, 977666666555, 976666666655, 966666666665}.

Proof. Since d_{n} ≤ d_{n−1} ≤ c_{n−1} + 1, it is clear that h = d_{n} must satisfy 0 ≤ h ≤ c_{n−1} + 1. We now broadly classify the degree sequences according to whether h = c_{n−1} + 1 (Case 1) or 0 ≤ h ≤ c_{n−1} (Case 2). Throughout the proof we use y as a notation for c_{h} (especially in the diagrams).

If h = c_{n−1} + 1, then d_{n−1} = h (since c_{n−1} can be at most one less than d_{n−1}, and d_{n−1} ≠ h − 1 because D is non-increasing). Since h becomes h − 1 in position n, it follows that either c_{h} = h (Case 1a) or c_{h} = h − 1 (Case 1b).

[Case 1a:]

Here we must have d_{h} = h and c_{q} = h − 1; there are thus n − q elements equal to h − 1. Also, the elements in positions 1 thru p get reduced; the only other elements that can be reduced would appear in the range p + 1 to h − 1. To get h elements of D reduced in obtaining C we must therefore have h ≥ p + n − q. On the other hand, if the last inequality holds, then the update given in the statement of the lemma does specify a D such that f(D) = C.

The proofs of the other cases follow by similar exhaustive reasoning and are omitted. We do provide some helpful diagrams.

[Case 1b:]

D C  y + 2  y + 1 y + 1  y  h^{s}  ^{p}  ^{h}

[Case 3:]

D C  y + 1  h y  y − 1^{p}  ^{q}^{a}  ^{b}

[Case 4:]

n\d_{1} 0 1 2 3 4  5  6  7  8  9  10 11
1 1
2 1 1
3 1 1 2
4 1 2 4 4
5 1 2 7 10 11
6 1 3 10 22 35 31
7 1 3 14 34 78 110 102
8 1 4 18 54 138 267 389 342
9 1 4 23 74 223 503 968 1352 1213
10 1 5 28 104 333 866 1927 3496 4895 4361
11 1 5 34 134 479 1356 3417 7221 12892 17793 16016

Table 2: Number of degree sequences classified by d_{1}.

D C  y + 1  y  h y + 1  y^{a}  ^{b}^{h}^{p}  ^{q}
□

Note that |f^{−1}(C)| > 1 unless C consists of all 0’s.

We may implement Theorem 5 in a fairly straightforward manner using recursion. A Pascal implementation may be found in the Appendix. We have used the algorithm to compute a table of the number of degree sequences of length n with largest degree d (see Table 2). Table 3 shows the result of running the algorithm for 1 ≤ n ≤ 16. The cost is the sum of the number of recursive calls together with a count of the number of times through all of the loops. This gives and accurate (up to constant factors as a function of n) measure of the amount of computation done by the algorithm. Since the cost is decreasing to some constant less than 4, we conclude that the algorithm is an alley CAT.

The enumeration of degree sequences appears to be at least as difficult as the enumeration of score sequences. See Stanley [15] and Peled [12] for some recent results on this question. It may therefore be rather difficult to obtain accurate statements about the cost as a function of n.

\begin{matrix}n & |D_{n}| & calls/|D_{n}| & cost/|D_{n}| & cost \\ 1 & 1 & 1.00000 & 0.00000 & 0 \\ 2 & 2 & 1.50000 & 2.50000 & 5 \\ 3 & 4 & 1.75000 & 5.00000 & 20 \\ 4 & 11 & 1.63636 & 5.00000 & 55 \\ 5 & 31 & 1.58065 & 5.35484 & 166 \\ 6 & 102 & 1.48039 & 4.65686 & 475 \\ 7 & 342 & 1.44152 & 4.53509 & 1551 \\ 8 & 1213 & 1.40643 & 4.21682 & 5115 \\ 9 & 4361 & 1.39119 & 4.13667 & 18040 \\ 10 & 16016 & 1.37881 & 4.02323 & 64436 \\ 11 & 59348 & 1.37209 & 3.97944 & 236172 \\ 12 & 222117 & 1.36661 & 3.92911 & 872722 \\ 13 & 836315 & 1.36296 & 3.89905 & 3260831 \\ 14 & 3166852 & 1.35994 & 3.86925 & 12253345 \\ 15 & 12042620 & 1.35762 & 3.84654 & 46322365 \\ 16 & 45967479 & 1.35567 & 3.82570 & 175857659 \end{matrix}

Table 3: The cost of generating degree sequences.

3.1 Degree Sequences of k-connected Graphs

There has been some interest in degree sequences of k-connected graphs. We say that a sequence is k-connected graphical if it there is some k-connected graph with that sequence as its sequence of degrees. The following theorem is to be found in Berge [3].

Theorem 6 A degree sequence is a 1-connected degree sequence if and only if d_{n} ≥ 1 and ∑_{i=1}^{n} d_{i} ≥ 2(n − 1).

More useful for our purposes is the following theorem of Asano [1].

Theorem 7 (Asano) A degree sequence D is 1-connected graphical if and only if f(D) is 1-connected graphical, or D = (1, 1).

To apply Theorem 7 to the problem of generating all graphical sequences we need only change the lower limit of the outer loop from 0 to 1.

What about k-connectivity? Consider D = 22222 with k = 2. Since f(D) = 2211 is not 2-connected graphical, Theorem 7 cannot be extended to k-connectedness. The following theorem of Wang and Kleitman [17] generalizes Berge’s result.

Theorem 8 (Wang-Kleitman) A degree sequence D is k-connected graphical if and only if n ≥ k + 1, d_{n} ≥ k, and

\frac{1}{2} ∑_{j=1}^{n} d_{j} ≥ n − \binom{k}{2} − 1 + ∑_{j=1}^{k−1} d_{j}

We observe the following corollary.

Corollary 2 If D is a degree sequence with d_{n} ≥ k, n ≥ k + 1, and d_{n−2} ≥ k + 1 then D is k-connected graphical.

Proof. We show that

d_{k} + ⋯ + d_{n} ≥ 2n − k(k − 1) − 2 + d_{1} + ⋯ + d_{k−1}

and then appeal to Theorem 8. Let p be such that d_{p} > k and d_{p+1} = k. The condition of the corollary implies that p ≥ n − 2.

d_{k} + ⋯ + d_{n} ≥ (k + 1)(p − k + 1) − k(n − p)
≥ 2n − k(k − 1) − 2 + (k − 1)(n − 1)
≥ 2n − k(k − 1) − 2 + d_{1} + ⋯ + d_{k−1}
□

We now consider 2-connected graphical sequences.

Lemma 1 Sequence D with n ≥ 3 is 2-connected if and only if either f(D) is 2connected or D = (2, 2, …, 2).

Proof. Assume that D is 2-connected but C = f(D) is not. Either c_{n−1} = 1 or c_{n−1} = 2 by Corollary 2.

If c_{n−1}, then d_{n−1} = d_{n} = 2. If d_{1} = 2, then D = (2, 2, …, 2) which is accounted for in the statement of the lemma. If d_{1} > 2 then D = (d, 2, 2, …, 2) where d ≥ 4; but this is not 2-connected by Theorem 8.

If c_{n−1} = 2, then by Corollary 2 c_{n−3} = c_{n−2} = c_{n−1} = 2. Now consider the two cases d_{n} = 3 and d_{n} = 2. If d_{n} = 3 then by the nature of f(D) we have d_{1} = d_{2} = ⋯ = d_{n} = 3, and C = (3, 3, …, 3, 2, 2, 2), which is 2-connected by Theorem 8. For d_{n} = 2 we now consider the two cases c_{1} = d_{1} − 1 and c_{1} = d_{1}.

If d_{n} = 2 and c_{1} = d_{1} − 1, then

∑_{i=1}^{n−1} c_{i} = −2d_{n} + ∑_{i=1}^{n} d_{i} (always holds)
= 2n − 8 + 2d_{1}
≥ 2n − 8 + 2(c_{1} + 1)
≥ 2(n − 1) − 4 + 2c_{1}

If d_{n} = 2 and c_{1} = d_{1}, then d_{1} = d_{2} = d_{3}. Now observe, since d_{3} > 2 and ∑_{i=1}^{n} d_{i} is even, that

d_{3} + ⋯ + d_{n} ≥ 2(n − 2) + 2,

and hence that

∑_{i=1}^{n−1} c_{i} = −4 + ∑_{i=1}^{n} d_{i}
≥ −4 + 2n − 4 + 2 + 2d_{1}
= 2n − 6 + 2d_{1}
= 2(n − 1) − 4 + 2c_{1}
□

4 Final Remarks

There are a number of other problems about generating various types of degree sequences that suggest themselves. We have solved some of these problems and are working on others. These results will be presented later in a more complete version of this paper.

One problem is to extend the results on connected and biconnected graphs to larger values of k-connectedness.

Another problem related to the ones considered in this paper is that of generating the corresponding sequences for digraphs that we called degree sequences for graphs. We define a sequence

(s_{1}, t_{1}), (s_{2}, t_{2}), …, (s_{p}, t_{p}) with s_{1} ≥ s_{2} ≥ ⋯ ≥ s_{p}  (2)

to be digraphical if the vertices of some digraph can be labelled 1, 2, …, n such that s_{i} is the outdegree of the vertex i and t_{i} is the indegree of vertex i. These sequences are characterized by the following theorem of Fulkerson [5] and Ryser [13].

Theorem 9 (Fulkerson-Ryser) A sequence as in (2) is digraphical if and only if the following three conditions hold.

(a) s_{i} ≤ p − 1 and t_{i} ≤ p − 1 for i = 1, 2, …, p, and

(b) ∑_{i=1}^{p} s_{i} = ∑_{i=1}^{p} t_{i}, and

(c)

∑_{i=1}^{n} s_{i} ≤ ∑_{i=1}^{n} min{p − 1, t_{i}} + ∑_{i=n+1}^{p} min{n, t_{i}} for 1 ≤ n < p.

Similarly, one may define bipartite graphical sequence pairs {S, T }, where S is the degree sequence of vertices in one partite set and T is the degree sequence of vertices in the other set. The following characterization is known (see Takahashi, Imai, and Asano [16]).

Theorem 10 Let S = (s_{1}, s_{2}, …, s_{n}) and T = (t_{1}, t_{2}, …, t_{m}) be a pair of nonnegative integer sequences with ∑_{i=1}^{n} s_{i} = ∑_{j=1}^{m} t_{j}, n ≥ s_{1} ≥ s_{2} ⋯ ≥ s_{n}, t_{1} ≤ t_{2} ≤ ⋯ ≤ t_{m}. Then {S, T } is bipartite graphical if and only if, for all i = 1, 2, …, n and j = 1, 2, …, m,

∑_{k=1}^{i} s_{k} ≤ i(m − j) + ∑_{k=1}^{j} t_{k}

Instead of generating all degree sequences with n vertices, we could consider the problem of generating all degree sequences of graphs with m edges and no isolated vertices (to ensure finiteness). Let g(m) be the number of such degree sequences and let p(m) be the number of integer partitions of m. A long-standing conjecture is that the limit, as m tends to infinity, of g(m)/p(m) is zero.

We have developed a representation of degree sequences that allows us to generate them in a CAT manner using essentially the same algorithm as that developed in this paper. This representation is a modified run-length encoding of the degree sequence.

5 Acknowledgement

The first author would like to thank the hospitality of the Department of Computer Science, University of Newcastle, Australia, where he spent his sabbatical and this research was conducted.

References

[1] T. Asano, “Graphical degree sequence problems with connectivity requirements”, Lecture Notes in Computer Science #762, (1993) 38-47.

[2] D. Avis and K. Fukuda, “Reverse Search for Enumeration”, Discrete Applied Mathematics, to appear.

[3] C. Berge, Graphes et Hypergraphes, Dunod, 1970.

[4] P. Erdös and T. Gallai, “Graphs with prescribed degrees of vertices (Hungarian)”, Mat. Lapok, 11 (1960) 264-274.

[5] D.R. Fulkerson, “ Zero-one matrices with zero traces”, Pacific J. Mathematics, 10 (1960) 831-836.

[6] S.V. Gervacio, “Score Sequences: Lexicographic Enumeration and Tournament Construction”, Discrete Mathematics, 72 (1988) 151-155.

[7] S. Hakimi, “On the realizability of a set of integers as degrees of the vertices of a graph”, SIAM J. Applied Math., 10 (1962) 496-506.

[8] V. Havel, “A remark on the existence of finite graphs (Hungarian)”, Časopis Pěst. Mat., 80 (1955) 477-480.

[9] H.G. Landau, “On dominance relations and the structure of animal societies, III. The condition for a score structure”, Bulletin for Mathematical Biophysics, 15 (1953) 143-148.

[10] John W. Moon, Topics on Tournaments, Holt, Rinehart, and Winston, 1968.

[11] T.V. Narayana, R.M. Mathsen, and J. Sarangi, “An algorithm for Generating Partitions and its Applications”, J. Combinatorial Theory (A), 11 (1971) 54-61.

[12] U.N. Peled and M.K. Srinivasan, The polytope of degree sequences, Linear Algebra Appl., 114 (1989) 349-377.

[13] H. Ryser, Combinatorial Mathematics, Carus Mathematical Monographs, MAA, 1963.

[14] C. Savage, personal communication.

[15] R.P. Stanley, A Zonotope Associated with Graphical Degree Sequences, manuscript, 1989, appeared in Applied Geometry and Discrete Math., 1991, Dimacs Series, AMS.

[16] M. Takahashi, K. Imai, and T. Asano, “Graphical Degree Sequence Problems”, Tech. Report TR93-AL-33-15, Information Processing Society of Japan, (1993) 111-118.

[17] D.L. Wang and D.J. Kleitman, “On the existence of n-connected graphs with prescribed degrees”, Networks, 3 (1973) 225-239.

[18] K.J. Winston and D.J. Kleitman, “On the asymptotic number of tournament score sequences”, J. Combinatorial Theory (A), 35 (1983) 208-230.

6 Appendix

In this Appendix we present our Pascal code to generate degree sequences.

program DegreeSequence;
var
d : array [0..100] of integer;
n,k,i : integer;
procedure PrintIt( n : integer );
var i : integer;
begin
for i := 1 to n do write( d[i]:2 );
writeln;
end {of PrintIt};
procedure gen ( k : integer );
var h,p,q,s,i,j,hval : integer;
begin
if k > n then PrintIt( n )
else begin
h := d[k-1] + 1;
hval := d[h];
p := h;  while d[p] = hval do p := p - 1;
q := h;  while d[q] = hval do q := q + 1;
if q > k then q := k;
{------ Case 1a: ------}
if d[h] = h then begin
   if p+k-q <= h then begin
      for i := 1 to h-k+q {p} do d[i] := d[i] + 1;
      for j := q to k-1 do d[j] := d[j] + 1;
      d[k] := h;  gen( k+1 );
      for i := 1 to h-k+q {p} do d[i] := d[i] - 1;
      for j := q to k-1 do d[j] := d[j] - 1;
   end;
end;
{------ Case 1b: ------}
if d[h] = h-1 then begin
   s := p;
   while d[s] = h do s := s-1;
   if s < 0 then s := 0;
   if s+k-p-1 <= h then begin

   for i := 1 to h-k+p+1 do d[i] := d[i] + 1;
   for j := p+1 to k-1 do d[j] := h;
   d[k] := h;  gen( k+1 );
   for i := 1 to h-k+p+1 do d[i] := d[i] - 1;
   for j := p+1 to k-1 do d[j] := h - 1;
end;
end;
{------ Case 2: ------}
for h := d[k-1] downto 0 do begin
hval := d[h];
p := h;  while d[p] = hval do p := p - 1;
q := h;  while d[q] = hval do q := q + 1;
if q > k then q := k;
d[k] := h;
for i := 1 to h do d[i] := d[i] + 1;
gen( k+1 );
i := h;  j := q;
while (i > p) and (d[j] = hval - 1) and (j < k) do begin
   d[j] := d[j] + 1;  j := j + 1;
   d[i] := d[i] - 1;  i := i - 1;
   gen( k+1 );
end;
for j := j-1 downto q do d[j] := d[j] - 1;
for i := i+1 to h do d[i] := d[i] + 1;
i := p;  j := h+1;
while (j < q) and (d[i] = d[i+1]+1) do begin
   d[i] := d[i] - 1;  i := i - 1;
   d[j] := d[j] + 1;  j := j + 1;
   gen( k+1 );
end;
for i := i+1 to p do d[i] := d[i] + 1;
for j := j-1 downto h+1 do d[j] := d[j] - 1;
for i := 1 to h do d[i] := d[i] - 1;
end;
end;
end {of gen};
begin
write( 'Enter n,k: ' ); readln( n,k );
if k > 1 then begin
write( 'Enter d[1..k-1]: ' );
for i := 1 to k-1 do read( d[i] );
readln;
end;
d[0] := n+1;
gen( k );
end.