% Latex file
% Algorithms for generating labelled graphs with given degree
% V. Fack and J. Van der Jeugt
% J. Comp. Appl. Math. 37 (1991) 187-194
%
\documentclass[12pt]{article}
\usepackage{latexsym,amssymb}
%
%
% The Greek symbols defined by the first two letters of their name
%
\def\al{\alpha}
\def\be{\beta}
\def\ga{\gamma}
\def\de{\delta}
\def\ep{\epsilon}  \def\vep{\varepsilon}
\def\ze{\zeta}
\def\et{\eta}
\def\th{\theta}
\def\io{\iota}
\def\ka{\kappa}
\def\la{\lambda}
\def\rh{\rho}
\def\si{\sigma}
\def\ta{\tau}
\def\ph{\phi}
\def\ch{\raise 2pt\hbox{$\chi$}}  % raise this a bit
\def\ps{\psi}
\def\om{\omega}
\def\Ga{\Gamma}
\def\De{\Delta}
\def\Th{\Theta}
\def\La{\Lambda}
\def\Si{\Sigma}
\def\Ph{\Phi}
\def\Ps{\Psi}
\def\Om{\Omega}
%
\def\beq{\begin{equation}}
\def\eeq{\end{equation}}
\def\bea{\begin{eqnarray}}
\def\eea{\end{eqnarray}}
\def\beas{\begin{eqnarray*}}
\def\eeas{\end{eqnarray*}}
\def\nn{\nonumber}
%
% the end-of-proof box
\def\mybox{\hfill\llap{$\Box$}}
%
\def\Nat{\mathbb{N}}
\def\Zah{\mathbb{Z}}
\def\Real{\mathbb{R}}
\def\Q{\mathbb{Q}}
\def\C{\mathbb{C}}
%
%
\setlength{\topmargin}{0cm}
\setlength{\oddsidemargin}{0cm}
\setlength{\evensidemargin}{0cm}
\setlength{\textheight}{225mm}
\setlength{\textwidth}{150mm}
%
% SOME MACROS FOR YOUNG DIAGRAMS
%
\def\mystrut{\hbox{\vrule height9.6pt depth2pt width0pt}}
\def\largestrut{\hbox{\vrule height 11.6pt depth 4pt width 0pt}}
\def\myrulefill{\leaders\hrule height1.4pt\hfill}
\def\myvrule{\vrule width1.4pt}
%
%
%
\begin{document}
%
\title{Algorithms for generating labelled graphs with given degree}
\author{V.~Fack and
J.~Van der Jeugt\thanks{Research Associate of the NFWO
(National Funds for Scientific Research of Belgium)} \\
{\normalsize Laboratorium voor Numerieke Wiskunde en Informatica,}\\
{\normalsize Rijksuniversiteit Gent, Krijgslaan 281-S9, B9000 Gent,
Belgium}}
%
\maketitle
%
\begin{center}
\sl The authors have great pleasure in dedicating this paper to
Prof.~Dr.~C.C.~Grosjean on the occasion of his sixty fifth birthday.
\end{center}
%
\vskip 1cm
%
\begin{abstract}
Using an isomorphism, due to Burge, between Young tableaux
of special shape and
(undirected) labelled graphs without loops or multiple edges,
we describe an algorithm to generate such graphs.
\end{abstract}
\vskip 5mm
\noindent {\sl Keywords~:} Labelled graphs, Young tableaux.\\
{\sl Short title~:} Generating labelled graphs.

\section{Introduction}

 Graph theory is one of the areas in mathematics that has enabled
scientists to develop elegant and ingenious algorithms for the solution
of a wide variety of problems~\cite{gi}.  The elegance, and in particular
properties such as polynomial time-complexity of these algorithms, often
comes from a certain symmetry or invariance in the original problem. 
Also, many graph theoretical algorithms present a solution to a question
of the following type~: given a {\sl fixed} graph $G$ (sometimes with
extra information), find $p$ ($p$ can be almost anything, e.g.~Eulerian
circuits, Hamiltonian tours, a shortest path from one vertex to another,
an edge- or vertex-colouring,$\ldots$). 

 In topics where the graph is not fixed but, on the contrary, part of
the solution (such as in questions of the form~: find all graphs $G$
satisfying a certain property $q$), the situation is often more
difficult and in fact few algorithms have been developed for problems of
this kind.  Moreover, in many practical situations the question can
involve a property of such a complicated form that the best solution is
often to generate all graphs of a particular type and test the property
on each of them. 

 In this paper we shall be dealing with a problem of the latter kind. 
Let us first decribe a practical situation where the problem occurs. 
Suppose $n$ systems (processors, work-stations, $\ldots$) $S_1, S_2,
\ldots, S_n$ are given, each of them having a fixed number of access
gates $d_i$ ($i=1,\ldots,n$).  Let $c_{ij}$ denote the cost of a
connection (a line) between $S_i$ and $S_j$, then what is the cheapest
configuration under the assumption that all gates are used? In such a
configuration, no connections from $S_i$ to itself and no multiple
connections between any pair $S_i$ and $S_j$ are allowed.  It is easy to
see that a configuration corresponds to an undirected labelled graph
with $n$ vertices $1,2,\ldots,n$ with given degree $d_i$, without loops
or multiple edges.  As there is no symmetry in the problem (provided a
lot of the degrees are distinct, and provided most of the costs $c_{ij}$
($i<j$) are distinct) the way to find a solution is to generate all the
graphs and to evaluate the cost on each of them.  So we are lead to
finding an efficient algorithm to generate all (undirected) labelled
graphs with given degree without loops or multiple edges.

 In the present paper we present two such algorithms. The first is
straightforward, generating all adjacency matrices corresponding to such
graphs. The second is more subtle, and makes use of a correspondence, due
to Burge, between Young tableaux of a particular kind and such graphs.
In order to understand the correspondence, we shall give a short
introduction to partitions and Young tableaux in Section~3. The
structure of the paper is as follows. Section~2 gives some general
definitions, and describes the obvious `brute force' algorithm
to solve the problem. Section~3 discusses partitions, Young diagrams
and Young tableaux, and is self-contained in the sense that no
pre-knowledge is required. In Section~4 Burge's correspondence is
given, and in Section~5 we discuss how the correspondence can be used
and implemented in order to generate all graphs of the type under
consideration.

\section{Graphs and adjacency matrices}

 A graph $G$ consists of a couple $G=(V,E)$, where $V$ is the set of
vertices or points $V=\{1,2,\ldots,n\}$ and $E$ is the set of edges~:
$E\subset V\times V$~\cite{be,gi}. As our graphs are undirected and without loops, we
can assume that $i<j$ for every edge $(i,j)\in E$; the fact that every edge
is specified by its end-points only implies immediately that we are
dealing with graphs without multiple edges.

The two end-points $i$ and $j$ of an edge $(i,j)\in E$ are called {\em
adjacent}, we denote this by $i \sim j$.
The adjacency relation $\sim$ is symmetric and antireflexive.
We can associate an $n \times n$ matrix $A$ with the graph in the following
way~:
\[
a_{ij} = \left\{
\begin{array}{ll}
1,&\mbox{if $i\sim j$,} \\
0,&\mbox{otherwise.}
\end{array}\right.
\]
Such a matrix is called an {\em adjacency matrix\/} of the graph.
Note that for the considered graphs an adjacency matrix is always symmetric
and has a diagonal consisting of all zeros.

The number of vertices adjacent to a given vertex $i$ of $G$ is called the
{\em degree\/} of the vertex $i$.
The number of 1's on row $i$ (or column $i$, because of the symmetry)
of the adjacency matrix is equal to the degree of vertex $i$ of $G$.

A straightforward way to generate all graphs with given degree consists
then in generating all possible adjacency matrices.
This can be done by a simple back-tracking algorithm {\tt GENADJ},
which successively
puts 0 and 1 at a specific matrix element $a_{ij}$ and `tries' in each case
to complete the rest of the matrix recursively. This way the matrix is
filled row by row; because of the symmetry only the upper diagonal part of
the matrix needs to be filled. 
At each stage so-called pruning methods are used to avoid generating dead
branches in the generation tree, the recursion only continues if the
matrix generated so far can still be a suitable adjacency matrix.
In particular we use the fact that the number of 1's on each row (and
column) is known, which results in the following pruning rules~:
  \begin{itemize}
  \item A row is completed with zeroes if it already contains enough ones.
  \item A row is completed with ones if the number of places left to be
    filled equals the number of ones left to be put. This might cause one
    of the columns to contain more than the required number of ones, in
    which case this `branch' is discarded.
  \end{itemize}
This algorithm is simple and easy to implement, however it is also a `brute
force' approach of the problem.
A better algorithm is introduced in the next sections.

\section{Partitions, Young diagrams and tableaux}

A partition $\la$ of a non-negative integer $N$ is a sequence $\la =
(\la_1,\ldots,\la_p,0,0,\ldots)$ of non-increasing integers
$\la_1\geq\ldots\geq\la_p>0$ with $\sum_i \la_i=N$~\cite{ma}.  The non-zero
$\la_i$ are called the parts of the partition, the number $p=l(\la)$ is
called the length of $\la$, and $N=|\la|$ is often called the weight of
the partition.  The Young diagram $F^\la$ of shape $\la$ is the set of
left-adjusted rows of squares with $\la_i$ squares (or boxes) in the
$i$th row (reading from top to bottom).  For example, the Young diagram
of $(5,3,1,1)$ is given by~:
 \beq
 F^\la =\quad \vcenter
 {\offinterlineskip
 \halign{&\mystrut\vrule#&\hbox to 11.6pt{\hss$#$\hss}\cr
   \multispan{11}\hrulefill\cr
   & && && && && &\cr
   \multispan{11}\hrulefill\cr
   & && && &\cr
   \multispan7\hrulefill\cr
   & &\cr
   \multispan3\hrulefill\cr
   & &\cr
   \multispan3\hrulefill\cr
   }}
 \eeq
 Every box in $F^\la$ has a position $(i,j)$ where $i$ is the row-index
(running from top to bottom) and $j$ is the column-index (running from
left to right), thus every position $(i,j)$ satisfies $1\leq i\leq p$
and $1\leq j\leq\la_i$.  The partition $\la'$ conjugate to $\la$
corresponds to the transposed diagram of $\la$, i.e.~to the diagram
obtained by reflecting $F^\la$ in the main diagonal.  For example, the
conjugate of $(5,3,1,1)$ is $(4,2,2,1,1)$~:
 \beq
 F^{\la'} =\quad \vcenter
 {\offinterlineskip
 \halign{&\mystrut\vrule#&\hbox to 11.6pt{\hss$#$\hss}\cr
   \multispan9\hrulefill\cr
   & && && && &\cr
   \multispan9\hrulefill\cr
   & && &\cr
   \multispan5\hrulefill\cr
   & && &\cr
   \multispan5\hrulefill\cr
   & &\cr
   \multispan3\hrulefill\cr
   & &\cr
   \multispan3\hrulefill\cr
   }}
 \eeq
 There is an alternative way to describe a partition $\la$ due to
Frobenius. Let the main diagonal of $F^\la$ consist of $r$ boxes $(i,i)$
($1\leq i \leq r$), and let $\al_i=\la_i-i$ be the number of boxes in
the $i$th row of $F^\la$ to the right of $(i,i)$ and $\be_i=\la_i'-i$ be
the number of boxes in the $i$th column of $F^\la$ below $(i,i)$. Then
$\al_1>\al_2>\cdots>\al_r\geq 0$ and $\be_1>\be_2>\cdots>\be_r\geq 0$,
and the Frobenius notation for $\la$ is given by
 \beq
 \la = \left( {\al_1 \atop \be_1} {\al_2 \atop \be_2}
   \cdots {\al_r \atop \be_r} \right) = \left({\al \atop \be}\right).
 \eeq
 Clearly, the conjugate of $\left({\al\atop\be}\right)$ is
$\left({\be\atop\al}\right)$~:
\beq
\left(\alpha\atop\beta\right) =
\vcenter
 {\offinterlineskip
 \halign{&\mystrut\vrule#&\hbox to 11.6pt{\hss$\scriptstyle#$\hss}\cr
  \multispan{17}\hrulefill\cr
  & && &\omit& &\omit& &\omit&\alpha_1&\omit& &\omit& &\omit& &\cr
  \multispan{17}\hrulefill\cr
  & && && &\omit& &\omit&\alpha_2&\omit& &\omit& &\omit& &\cr
  \omit\vrule&\omit&\multispan{15}\hrulefill\cr
  & && && && &\omit&\alpha_3&\omit& &\cr
  \omit\vrule&\omit&\omit\vrule&\omit&\multispan9\hrulefill\cr
  & && && &&\scriptscriptstyle\cdots\cr
  &\beta_1&&\beta_2&&\beta_3&\cr
  & && && &\cr
  \omit\vrule&\omit&\omit\vrule&\multispan4\hrulefill\cr
  & &\cr
  \omit\vrule&\omit&\omit\vrule\cr
  & &\cr
  \multispan3\hrulefill\cr
   }}
\qquad \qquad
\left(\beta\atop\alpha\right) =
\vcenter
 {\offinterlineskip
 \halign{&\mystrut\vrule#&\hbox to 11.6pt{\hss$\scriptstyle#$\hss}\cr
  \multispan{17}\hrulefill\cr
  & && &\omit& &\omit& &\omit&\beta_1&\omit& &\omit& &\omit& &\cr
  \multispan{17}\hrulefill\cr
  & && && &\omit& &\omit&\beta_2&\omit& &\cr
  \omit\vrule&\omit&\multispan{11}\hrulefill\cr
  & && && && &\omit&\beta_3&\omit& &\cr
  \omit\vrule&\omit&\omit\vrule&\omit&\multispan9\hrulefill\cr
  & && && &&\scriptscriptstyle\cdots\cr
  &\alpha_1&&\alpha_2&&\alpha_3&\cr
  & && && &\cr
  \omit\vrule&\omit&\omit\vrule&\omit&\multispan3\hrulefill\cr
  & && &\cr
  \omit\vrule&\omit&\omit\vrule&\omit&\omit\vrule\cr
  & && &\cr
  \multispan5\hrulefill\cr
   }}
\eeq

A column-strict Young tableau $T$ of shape $\la$ is a numbering of the
boxes of $F^\la$ with non-negative integers such that the numbers
increase strictly down columns and increase weakly from left to right
across rows~\cite{ma,st}.  For example~:
 \beq
 T =\quad \vcenter
 {\offinterlineskip
 \halign{&\mystrut\vrule#&\hbox to 11.6pt{\hss$#$\hss}\cr
   \multispan{11}\hrulefill\cr
   &1&&1&&2&&2&&4&\cr
   \multispan{11}\hrulefill\cr
   &2&&3&&3&\cr
   \multispan7\hrulefill\cr
   &3&\cr
   \multispan3\hrulefill\cr
   &4&\cr
   \multispan3\hrulefill\cr
   }}
 \eeq

Schensted~\cite{sc} was the first to introduce an operation {\tt INSERT} on a
Young tableau.  {\tt INSERT} gives a way of inserting a given number $k$
into a given tableau $T$ such that the new tableau which is one box
larger than $T$ is again column-strict.  A new element is inserted into
$T$ by comparing it with the numbers in the first row and displacing the
first larger found when reading from left to right.  If there is no
larger, the entering item is added to the end of the row.  If an item is
displaced or ``bumped'', it is inserted into the second and subsequent
rows of the tableau in the same way.  For example, inserting 5 in $T$
gives $S_1$, and inserting 1 in $T$ gives $S_2$~:
 \beq
 S_1 =\quad \vcenter
 {\offinterlineskip
 \halign{&\mystrut\vrule#&\hbox to 11.6pt{\hss$#$\hss}\cr
   \multispan{13}\hrulefill\cr
   &1&&1&&2&&2&&4&&5&\cr
   \multispan{13}\hrulefill\cr
   &2&&3&&3&\cr
   \multispan7\hrulefill\cr
   &3&\cr
   \multispan3\hrulefill\cr
   &4&\cr
   \multispan3\hrulefill\cr
   }}\quad , \qquad
 S_2 =\quad \vcenter
 {\offinterlineskip
 \halign{&\mystrut\vrule#&\hbox to 11.6pt{\hss$#$\hss}\cr
   \multispan{11}\hrulefill\cr
   &1&&1&&1&&2&&4&\cr
   \multispan{11}\hrulefill\cr
   &2&&2&&3&\cr
   \multispan7\hrulefill\cr
   &3&&3&\cr
   \multispan5\hrulefill\cr
   &4&\cr
   \multispan3\hrulefill\cr
   }}\,.
 \eeq
 In the first case, there is no larger element than the new element 5 in
the first row of $T$, so 5 is placed at the end of the first row.  In
the second example with $k=1$, the number 2 at position $(1,3)$ is the
first element in the first row larger than 1, thus 1 takes the place of
2 and 2 is bumped to the second row.  To insert 2 in the second row,
note that 3 at position $(2,2)$ is the first element in the second row
larger than 2, thus 2 displaces 3 and 3 is bumped to the third row.
Here, there is no larger element than 3, so 3 is placed at the end of
the third row.

 It is known that the result of inserting a new integer into a tableau
is a proper column-strict Young tableau~\cite{kn}.  Moreover, the insertion
algorithm also defines a position $(s,t)$ at which the original tableau
$T$ has been extended.  In the examples, $(s,t)=(1,6)$ in the first case
and $(s,t)=(3,2)$ in the second case.

 The main property of this insertion algorithm is that it can be
reversed~\cite{kn}.  Given a tableau $S$ and a position $(s,t)$, there exists a
deleting algorithm {\tt DELETE} which recovers the entering element $k$
if $S$ was obtained by inserting $k$ into $T$ yielding position $(s,t)$.
The deleting algorithm
removes the element in position $(s,t)$ and uses it to bump the first
smaller element in the row above reading from right to left. This bumped
element is used in the same way in the rows above it until an element is
bumped from the first row. For example, deleting the position (4,1) in
$T$ given by (5) works as follows~: the 4 is removed from the fourth row and
bumps the 3 in the third row, this 3 comes in the second row at the
position of the 2 which is bumped to the first row, where it takes the
position of the rightmost 1. Thus the outcoming element is 1 and the
remaining tableau is
 \beq
 \vcenter
 {\offinterlineskip
 \halign{&\mystrut\vrule#&\hbox to 11.6pt{\hss$#$\hss}\cr
   \multispan{11}\hrulefill\cr
   &1&&2&&2&&2&&4&\cr
   \multispan{11}\hrulefill\cr
   &3&&3&&3&\cr
   \multispan7\hrulefill\cr
   &4&\cr
   \multispan3\hrulefill\cr
   }} \,.
 \eeq
 One can easily check that {\tt INSERT}(1) into this tableau yields (5).

\section{The correspondence of Burge}

Let $G=(V,E)$ be an undirected graph on $n$ vertices, without loops or multiple
edges. For example, let $n=6$ and the edges be given by
 \beq
 (1,2)\,, (1,4)\,, (2,5)\,, (3,5)\,, (3,6)\,, (5,6)\,.
 \eeq
 Here, a graph will be represented by a two-line array
 \beq
 \left({u_1\atop v_1}{u_2\atop v_2}\cdots{u_m\atop v_m}\right)\,,
 \eeq
 in which each pair $(u_k,v_k)$ is an edge of the graph with $u_k>v_k$
and the array is arranged such that $u_k\leq u_{k+1}$ and if
$u_k=u_{k+1}$ then $v_k>v_{k+1}$. So the two-line array corresponding to
(8) is given by
 \beq
 \left(\begin{array}{cccccc}
       2&4&5&5&6&6\\
       1&1&3&2&5&3
       \end{array} \right) \,.
 \eeq
 An algorithm {\tt MAKETAB}, due to Burge~\cite{bu}, will associate to every such
graph $G$ a column-strict Young tableau of the particular Frobenius form
 \beq
 \left(
 {\al_1\atop \al_1+1}\quad
 {\al_2\atop \al_2+1}\quad
 \ldots \quad
 {\al_r\atop \al_r+1}
 \right)
 \eeq
 Thus there is a dividing line to the left of and below the boxes on the
leading diagonal of such a tableau, which divides the diagram into two
equal `triangular' pieces, as shown in figure~(12).
Each position of a tableau of shape~(11)
corresponds to an opposite position in the same place in the other
triangular region.  For example, in the following tableau of Frobenius
shape $\left({3\atop 4}{1\atop 2}\right)$, opposite positions are
labelled by the same letter~:
 \beq
 \vcenter
 {\offinterlineskip
 \halign{&\largestrut\vrule#&\hbox to 15.6pt{\hss$#$\hss}\cr
   \multispan{9}\hrulefill\cr
   \omit\myvrule&f&&g&&h&&i&\cr
   \multispan3\myrulefill&\omit\hrulefill&\omit\vrule&\omit
     \hrulefill&\omit\vrule&\omit\hrulefill&\omit\vrule\cr
   &f&\omit\myvrule&j&&k&\cr
   \omit\vrule&\omit\hrulefill&\multispan3\myrulefill&\omit
     \hrulefill&\omit\vrule\cr
   &g&&j&\cr
   \multispan5\hrulefill\cr
   &h&&k&\cr
   \multispan5\hrulefill\cr
   &i&\cr
   \multispan3\hrulefill\cr
   }} \,.
 \eeq
 Thus the position opposite to $(s,t)$ is $(t+1,s)$ if $s\leq t$ and
$(t,s-1)$ otherwise.

 The algorithm {\tt MAKETAB} uses the two-line representation of $G$,
and each addition of a pair $(u_k,v_k)$ transforms the tableau of
shape~(11) obtained so far into a new tableau of Frobenius shape~(11). {\tt
MAKETAB}  works as follows~: (1) start from the empty tableau ; (2) for
$k=1,2,\ldots,m$, {\tt INSERT}($v_k$) which determines a position
$(s_k,t_k)$ and then place $u_k$ in the position opposite to
$(s_k,t_k)$. It has been shown that this produces indeed a column-strict
Young tableau~\cite{bu}. In the example~(10), the tableaux obtained
at each step are as follows~:
 \beq
 \vcenter
 {\offinterlineskip
 \halign{&\mystrut\vrule#&\hbox to 11.6pt{\hss$#$\hss}\cr
   \multispan3\hrulefill\cr
   &1&\cr
   \multispan3\hrulefill\cr
   &2&\cr
   \multispan3\hrulefill\cr
   }} \,,\quad
 \vcenter
 {\offinterlineskip
 \halign{&\mystrut\vrule#&\hbox to 11.6pt{\hss$#$\hss}\cr
   \multispan5\hrulefill\cr
   &1&&1&\cr
   \multispan5\hrulefill\cr
   &2&\cr
   \multispan3\hrulefill\cr
   &4&\cr
   \multispan3\hrulefill\cr
   }} \,,\quad
 \vcenter
 {\offinterlineskip
 \halign{&\mystrut\vrule#&\hbox to 11.6pt{\hss$#$\hss}\cr
   \multispan7\hrulefill\cr
   &1&&1&&3&\cr
   \multispan7\hrulefill\cr
   &2&\cr
   \multispan3\hrulefill\cr
   &4&\cr
   \multispan3\hrulefill\cr
   &5&\cr
   \multispan3\hrulefill\cr
   }} \,,\quad
 \vcenter
 {\offinterlineskip
 \halign{&\mystrut\vrule#&\hbox to 11.6pt{\hss$#$\hss}\cr
   \multispan7\hrulefill\cr
   &1&&1&&2&\cr
   \multispan7\hrulefill\cr
   &2&&3&\cr
   \multispan5\hrulefill\cr
   &4&&5&\cr
   \multispan5\hrulefill\cr
   &5&\cr
   \multispan3\hrulefill\cr
   }} \,,\quad
 \vcenter
 {\offinterlineskip
 \halign{&\mystrut\vrule#&\hbox to 11.6pt{\hss$#$\hss}\cr
   \multispan{9}\hrulefill\cr
   &1&&1&&2&&5&\cr
   \multispan{9}\hrulefill\cr
   &2&&3&\cr
   \multispan5\hrulefill\cr
   &4&&5&\cr
   \multispan5\hrulefill\cr
   &5&\cr
   \multispan3\hrulefill\cr
   &6&\cr
   \multispan3\hrulefill\cr
   }} \,,\quad
 \vcenter
 {\offinterlineskip
 \halign{&\mystrut\vrule#&\hbox to 11.6pt{\hss$#$\hss}\cr
   \multispan{9}\hrulefill\cr
   &1&&1&&2&&3&\cr
   \multispan{9}\hrulefill\cr
   &2&&3&&5&\cr
   \multispan7\hrulefill\cr
   &4&&5&\cr
   \multispan5\hrulefill\cr
   &5&&6&\cr
   \multispan5\hrulefill\cr
   &6&\cr
   \multispan3\hrulefill\cr
   }} \,.
 \eeq
 There exists a reverse operation {\tt MAKEARRAY} which produces a
two-line array (and thus a graph) from any given Young tableau of
shape~(11). It works as follows~: for $k=m,m-1,\ldots,1$ select the copy
of the largest integer in the tableau in the column with greatest index
as $u_k$, then use {\tt DELETE} on the opposite position~: the element
that bumps out is $v_k$.

\section{Generating all graphs using tableaux}

Let $G=(V,E)$ be a graph of the type under consideration, with
$V=\{1,2,\ldots,n\}$.  Suppose the degrees are $d_1,d_2,\ldots,d_n$,
with $d=\sum_i d_i$.  Then $d$ is even and $m=d/2$ is the number of
edges of $G$.  It is clear from the correspondence discussed in
Section~4 that the tableau $T$ associated to $G$ satisfies the following
property~: the number $i$ appears $d_i$ times in $T$ ($i=1,\ldots,n$).  As a
consequence of Burge's correspondence, in order to generate all graphs
of given type with fixed degrees $d_i$, we have to generate all
column-strict Young tableaux with $d_1$ 1's, $d_2$ 2's, $\ldots$, $d_n$
$n$'s, of Frobenius shape~(11).

Rather than generate all such tableaux with $d_i$ $i$'s and then select
the ones of the correct Frobenius shape, one can proceed as follows.

First, determine all partitions of $m$ into distinct integers not
exceeding $n-1$~: $m=a+b+c+\cdots$ with $n>a>b>c\cdots>0$. 
This can be done recursively by a back-tracking algorithm, {\tt PARTITIONS}.
With such a
partition corresponds a Young diagram of Frobenius shape
$\left({a-1\atop a}\,{b-1\atop b}\,{c-1\atop c}\cdots\right)$, namely
 \beq
 \vcenter
 {\offinterlineskip
 \halign{&\mystrut\vrule#&\hbox to 11.6pt{\hss$#$\hss}\cr
  \multispan{15}\hrulefill\cr
  & &\omit& &\omit& &\omit&a&\omit& &\omit& &\omit& &\cr
  \multispan{15}\hrulefill\cr
  & && &\omit& &\omit&b&\omit& &\omit& &\cr
  \omit\vrule&\omit&\multispan{11}\hrulefill\cr
  & && && &\omit&c&\omit& &\cr
  \omit\vrule&\omit&\omit\vrule&\omit&\multispan7\hrulefill\cr
  & && && &&\scriptscriptstyle\cdots\cr
  &a&&b&&c&\cr
  & && && &\cr
  \omit\vrule&\omit&\omit\vrule&\omit&\multispan3\hrulefill\cr
  & && &\cr
  \omit\vrule&\omit&\multispan3\hrulefill\cr
  & &\cr
  \multispan3\hrulefill\cr
   }}\qquad\hbox{of shape }
 \left({a-1\atop a}\,{b-1\atop b}\,{c-1\atop c}\cdots\right)\,.
 \eeq
 The requirement that the partition of $m$ must be into distinct
integers comes from the fact that we want a regular Young diagram.  The
requirement that the parts of the partition should not exceed $n-1$ is
because the actual Young diagram should have at most $n$ rows.  Indeed,
once the Young diagram of shape~(14) is going to be filled with $d_1$ 1's,
$d_2$ 2's, $\ldots$, $d_n$ $n$'s, in order to make a column-strict
tableau, the entries in the first column are strictly increasing, so
there cannot be more than $n$ rows. 

For every Frobenius shape obtained,
one has to determine all possible ``fillings'' with $d_i$ $i$'s leading
to a genuine column-strict Young tableau.
This can be done by a recursive back-tracking algorithm {\tt FILLTAB}.
The elements are put in the following order~: first the $d_1$ 1's, next the
$d_2$ 2's, \ldots, and finally the $d_n$ $n$'s.
At each level of the recursion, all possible positions for the `next'
element to be put, such that the Young tableau property is not violated,
are determined. The element is successively put at each of those positions,
and the next levels then recursively try to complete this tableau to a Young
tableau.
Sometimes there will be no possible positions to put the `next' element, in
that case the tableau is discarded, since it is impossible to complete it
to a Young tableau.

\begin{table}
\begin{center}
\begin{tabular}{|c||r|r|}
\hline
$d_1,\ldots,d_8$ & {\tt FILLTAB} &
 {\tt GENADJ}\\
\hline
4 4 3 3 2 2 1 1  & 8.7 & 11.1 \\
4 3 4 3 2 1 2 1  & 10.4 & 12.9 \\
4 3 2 1 4 3 2 1  & 15.8 & 14.6 \\
3 4 2 3 1 4 2 1  & 21.2 & 16.3 \\
4 3 2 1 1 2 3 4  & 56.4 & 14.8 \\
1 1 2 2 3 3 4 4  & 60.1 & 29.4 \\
\hline
\end{tabular}
\end{center}
\caption{
Running times in CPU seconds
of {\tt FILLTAB} and {\tt GENADJ} for different
orderings of the degrees $d_i$.}
\end{table}

Empirically we observe that reordering the $d_i$'s such that
$ d_1 \ge d_2 \ge \ldots \ge d_n $ usually results in fewer dead
branches, and that this is true for both algorithms {\tt FILLTAB} and
{\tt GENADJ}.
This can clearly be seen in Table~1, where
the running times in CPU seconds
are given for {\tt FILLTAB} and {\tt GENADJ}, for the
graphs with $n=8$ and $\{d_1,\ldots,d_8\}=\{4,4,3,3,2,2,1,1\}$.
It is interesting to note that as the large values
of $d_i$ appear closer to the end of the
sequence $(d_1,\ldots,
d_8)$, the running times are increasing considerably, the increase being
most notable for {\tt FILLTAB}. Knowing the way in which diagrams are filled
using {\tt FILLTAB}, the influence of the ordering of $d_i$ on the running time
is not surprising.

\begin{table}
\begin{center}
\begin{tabular}{|c|r||r|r|r|}
\hline
$n$ & $d_1,\ldots,d_n$ & number    & {\tt FILLTAB} & {\tt GENADJ} \\
    &                  & of graphs &               &              \\
\hline
7 & 5 4 3 3 2 2 1 & 32 & 1.1 & 0.8 \\
7 & 5 4 4 3 3 2 1 & 32 & 1.3 & 1.0 \\
7 & 4 4 3 3 2 1 1 & 39 & 1.1 & 1.2 \\
7 & 3 3 2 2 2 1 1 & 130 & 2.0 & 2.0 \\
8 & 6 5 5 4 3 3 2 2 & 273 & 8.2 & 6.2 \\
8 & 3 3 3 2 2 1 1 1 & 570 & 6.7 & 9.5 \\
8 & 4 4 3 3 2 2 1 1 & 581 & 8.7 & 11.1 \\
8 & 4 3 3 3 2 2 2 1 & 1972 & 32.6 & 31.7 \\
9 & 5 5 4 3 3 2 2 1 1 & 2399 & 38.0 & 53.7 \\
9 & 4 3 3 3 2 2 1 1 1 & 4569 & 52.4 & 83.5 \\
9 & 3 3 3 2 2 2 1 1 1 & 5418 & 58.7 & 89.8 \\
9 & 4 4 3 3 2 2 2 1 1 & 8180 & 107.0 & 141.8 \\
\hline
\end{tabular}
\end{center}
\caption{
Running times in CPU seconds of {\tt FILLTAB} and {\tt GENADJ} for a number
of cases with $n=7,8,9$.}
\end{table}

As for comparing the efficiency of the algorithms {\tt FILLTAB}
and {\tt GENADJ},
it is obvious that the generation tree of {\tt FILLTAB}
is much smaller than the generation tree of {\tt GENADJ}
for the same parameters, but that more work is done at each node
of the generation tree of {\tt FILLTAB}.
However, as can be seen from Table~2, where we list the running
times for both algorithms for several examples, in general {\tt FILLTAB}
is considerably faster than {\tt GENADJ}.
For completeness, we have
also tabulated the total number of graphs generated by the programs.
It can be observed that the running
times are approximately proportional to the total number of graphs
generated.

The algorithms described in this paper have been implemented in
{\tt MIKE}~\cite{co}, a new programming language developed by
K.~Coolsaet as part of the CAGe computer algebra project at the State
University of Ghent. The language is intended to be a general
programming language with a high level of abstraction, in particular,
but not exclusively, well suited for the implementation of computer
algebra algorithms. A typical feature of the language which was very
useful in our implementation, is the transparant memory management,
which makes it very easy to work with variable dimension arrays
(specifying the dimensions at runtime) and with lists without having
to worry about pointers. Upon request, the programs (as well as the
programming language environment) are available from the authors.
%
\begin{thebibliography}{99}
\bibitem{be}
C.~Berge, {\sl Graphs and Hypergraphs} (North Holland, Amsterdam, 1973)
\bibitem{bu}
W.H.~Burge, Four correspondences between graphs and generalized
Young tableaux, {\sl J.\ Combinatorial Theory A} {\bf 17} (1974), 12--30
\bibitem{co}
K.~Coolsaet, Preliminary report on the programming language MIKE
(Reports of the CAGe project State University of Ghent, 1989)
\bibitem{gi}
A.~Gibbons, {\sl Algorithmic Graph Theory} (Cambridge University Press, 1985)
\bibitem{kn}
D.E.~Knuth, Permutations, matrices, and generalized Young tableaux,
{\sl Pacific Journ.\ of Math.} {\bf 34} (1970), 709--727
\bibitem{ma}
I.G.~Macdonald, {\sl Symmetric functions and Hall polynomials}
(Oxford University Press, 1979)
\bibitem{sc}
C.~Schensted, Longest increasing and decreasing subsequences,
{\sl Canadian J.\ Math.} {\bf 13} (1961), 179--191
\bibitem{st}
R.P.~Stanley, Theory and applications of plane partitions I,
{\sl Stud.\ Appl.\ Math.} {\bf 50} (1971), 167--188
\end{thebibliography}
%
\end{document}