Degree sequences
The present module implements the DegreeSequences class, whose instances
represent the integer sequences of length :
sage: DegreeSequences(6)
Degree sequences on 6 elements
With the object DegreeSequences(n), one can :
Check whether a sequence is indeed a degree sequence
sage: DS = DegreeSequences(5) sage: [4, 3, 3, 3, 3] in DS True sage: [4, 4, 0, 0, 0] in DS FalseList all the possible degree sequences of length
:
sage: for seq in DegreeSequences(4): ... print seq [0, 0, 0, 0] [1, 1, 0, 0] [2, 1, 1, 0] [3, 1, 1, 1] [1, 1, 1, 1] [2, 2, 1, 1] [2, 2, 2, 0] [3, 2, 2, 1] [2, 2, 2, 2] [3, 3, 2, 2] [3, 3, 3, 3]
Note
Given a degree sequence, one can obtain a graph realizing it by using sage.graphs.graph_generators.graphs.DegreeSequence(). For instance
sage: ds = [3, 3, 2, 2, 2, 2, 2, 1, 1, 0]
sage: g = graphs.DegreeSequence(ds)
sage: g.degree_sequence()
[3, 3, 2, 2, 2, 2, 2, 1, 1, 0]
A sequence of integers is said to be a degree sequence (or
graphic sequence) if there exists a graph in which vertex
is of degree
. It is often required to be non-increasing, i.e. that
.
An integer sequence need not necessarily be a degree sequence. Indeed, in a
degree sequence of length no integer can be larger than
– the degree
of a vertex is at most
– and the sum of them is at most
.
Degree sequences are completely characterized by a result from Erdos and Gallai:
Erdos and Gallai: The sequence of integers is a
degree sequence if and only if
is even and
Alternatively, a degree sequence can be defined recursively :
Havel and Hakimi: The sequence of integers is a
degree sequence if and only if
is
also a degree sequence.
Or equivalently :
Havel and Hakimi (bis): If there is a realization of an integer sequence as
a graph (i.e. if the sequence is a degree sequence), then it can be realized in
such a way that the vertex of maximum degree is adjacent to the
vertices of highest degree (except itself, of course).
Checking whether a given sequence is a degree sequence
This is tested using Erdos and Gallai’s criterion. It is also checked that the
given sequence is non-increasing and has length .
Iterating through the sequences of length
From Havel and Hakimi’s recursive definition of a degree sequence, one can build
an enumeration algorithm as done in [RCES]. It consists in trying to extend
a current degree sequence on elements into a degree sequence on
elements by adding a vertex of degree larger than those already present in the
sequence. This can be seen as reversing the reduction operation described in
Havel and Hakimi’s characterization. This operation can appear in several
different ways :
Extensions of a degree sequence that do not change the value of the maximum element
If the maximum element of a given degree sequence is
, then one can remove it to reduce the sequence, following Havel and Hakimi’s rule. Conversely, if the maximum element of the (current) sequence is
, then one can always extend it by adding a new element of degree
to the sequence.
If there are at least
elements of (maximum) degree
in a given degree sequence, then one can reduce it by removing a vertex of degree
and decreasing the values of
elements of value
to
. Conversely, if the maximum element of the (current) sequence is
, then one can add a new element of degree
to the sequence if it can be linked to
elements of (current) degree
. Those
vertices of degree
hence become vertices of degree
, and so
elements of degree
are removed from the sequence while
elements of degree
are added to it.
Extension of a degree sequence that changes the value of the maximum element :
In the general case, i.e. when the number of elements of value
is small compared to
(i.e. the maximum element of a given degree sequence), reducing a sequence strictly decreases the value of the maximum element. According to Havel and Hakimi’s characterization there is only one way to reduce a sequence, but reversing this operation is more complicated than in the previous cases. Indeed, the following extensions are perfectly valid according to the reduction rule.
In order to extend a current degree sequence while strictly increasing its maximum degree, it is equivalent to pick a set
of elements of the degree sequence with
in such a way that the
are the
maximum elements of the sequence
, and to add to this new sequence an element of value
. The non-increasing sequence containing the elements
and
can be reduced to
by Havel and Hakimi’s rule.
The number of possible sets
having this property (i.e. the number of possible extensions of a sequence) is smaller than it seems. Indeed, by definition, if
then for all
the inequality
holds. Hence, each set
is entirely determined by the largest element
of the sequence that it does not contain (hence
contains
), and by the cardinalities of
and
.
The number of possible extensions is hence at most cubic, and is easily enumerated.
In the actual implementation of the enumeration algorithm, the degree sequence is stored differently for reasons of efficiency.
Indeed, when enumerating all the degree sequences of length , Sage first
allocates an array seq of
integers where seq[i] is the number of
elements of value i in the current sequence. Obviously, seq[n]=0 holds
in permanence : it is useful to allocate a larger array than necessary to
simplify the code. The seq array is a global variable.
The recursive function enum(depth, maximum) is the one building the list of
sequences. It builds the list of degree sequences of length which extend
the sequence currently stored in seq[0]...seq[depth-1]. When it is called,
maximum must be set to the maximum value of an element in the partial
sequence seq[0]...seq[depth-1].
If during its run the function enum heavily works on the content of the seq array, the value of seq is the same before and after the run of enum.
Extending the current partial sequence
The two cases for which the maximum degree of the partial sequence does not
change are easy to detect. It is (sligthly) harder to enumerate all the sets
corresponding to possible extensions of the partial sequence. As said
previously, to each set
one can associate an integer current_box such
that
contains all the
satisfying
. The variable
taken represents the number of all such elements
, so that when
enumerating all possible sets
in the algorithm we have the equality
[RCES] Alley CATs in search of good homes Ruskey, R. Cohen, P. Eades, A. Scott Congressus numerantium, 1994 Pages 97–110
Nathann Cohen
The sequences produced by random graphs are degree sequences:
sage: n = 30
sage: DS = DegreeSequences(30)
sage: for i in range(10):
... g = graphs.RandomGNP(n,.2)
... if not g.degree_sequence() in DS:
... print "Something is very wrong !"
Checking that we indeed enumerate all the degree sequences for :
sage: ds1 = Set([tuple(g.degree_sequence()) for g in graphs(5)])
sage: ds2 = Set(map(tuple,list(DegreeSequences(5))))
sage: ds1 == ds2
True
Checking the consistency of enumeration and test:
sage: DS = DegreeSequences(6)
sage: all(seq in DS for seq in DS)
True
Warning
For the moment, iterating over all degree sequences involves building the
list of them first, then iterate on this list. This is obviously bad, as it
requires uselessly a lot of memory for large values of .
As soon as the yield keyword is available in Cython this should be changed. Updating the code does not require more than a couple of minutes.
Degree Sequences
An instance of this class represents the degree sequences of graphs on a
given number of vertices. It can be used to list and count them, as
well as to test whether a sequence is a degree sequence. For more
information, please refer to the documentation of the
DegreeSequence module.
EXAMPLE:
sage: DegreeSequences(8)
Degree sequences on 8 elements
sage: [3,3,2,2,2,2,2,2] in DegreeSequences(8)
True