Degree sequences#
The present module implements the DegreeSequences
class, whose instances
represent the integer sequences of length \(n\):
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 False
List all the possible degree sequences of length \(n\):
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
DegreeSequence()
.
For instance:
sage: ds = [3, 3, 2, 2, 2, 2, 2, 1, 1, 0]
sage: g = graphs.DegreeSequence(ds) # needs networkx sage.graphs
sage: g.degree_sequence() # needs networkx sage.graphs
[3, 3, 2, 2, 2, 2, 2, 1, 1, 0]
Definitions#
A sequence of integers \(d_1,...,d_n\) is said to be a degree sequence (or graphic sequence) if there exists a graph in which vertex \(i\) is of degree \(d_i\). It is often required to be non-increasing, i.e. that \(d_1 \geq ... \geq d_n\). Finding a graph with given degree sequence is known as graph realization problem.
An integer sequence need not necessarily be a degree sequence. Indeed, in a degree sequence of length \(n\) no integer can be larger than \(n-1\) – the degree of a vertex is at most \(n-1\) – and the sum of them is at most \(n(n-1)\).
Degree sequences are completely characterized by a result from Erdős and Gallai:
Erdős and Gallai: The sequence of integers \(d_1 \geq \cdots \geq d_n\) is a degree sequence if and only if \(\sum_i d_i\) is even and \(\forall i\)
Alternatively, a degree sequence can be defined recursively:
Havel and Hakimi: The sequence of integers \(d_1\geq ... \geq d_n\) is a degree sequence if and only if \(d_2-1,...,d_{d_1+1}-1, d_{d_1+2}, ...,d_n\) 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 \(\Delta\) is adjacent to the \(\Delta\) vertices of highest degree (except itself, of course).
Algorithms#
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 \(n\).
Iterating through the sequences of length \(n\)
From Havel and Hakimi’s recursive definition of a degree sequence, one can build an enumeration algorithm as done in [RCES1994]. It consists in trying to extend a current degree sequence on \(n\) elements into a degree sequence on \(n+1\) 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 \(0\), 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 \(0\), then one can always extend it by adding a new element of degree \(0\) to the sequence.
\[0, 0, 0 \xrightarrow{Extension} {\bf 0}, 0, 0, 0 \xrightarrow{Extension} {\bf 0}, 0, 0, ..., 0, 0, 0 \xrightarrow{Reduction} 0, 0, 0, 0 \xrightarrow{Reduction} 0, 0, 0\]If there are at least \(\Delta+1\) elements of (maximum) degree \(\Delta\) in a given degree sequence, then one can reduce it by removing a vertex of degree \(\Delta\) and decreasing the values of \(\Delta\) elements of value \(\Delta\) to \(\Delta-1\). Conversely, if the maximum element of the (current) sequence is \(d>0\), then one can add a new element of degree \(d\) to the sequence if it can be linked to \(d\) elements of (current) degree \(d-1\). Those \(d\) vertices of degree \(d-1\) hence become vertices of degree \(d\), and so \(d\) elements of degree \(d-1\) are removed from the sequence while \(d+1\) elements of degree \(d\) are added to it.
\[3, 2, 2, 2, 1 \xrightarrow{Extension} {\bf 3}, 3, (2+1), (2+1), (2+1), 1 = {\bf 3}, 3, 3, 3, 3, 1 \xrightarrow{Reduction} 3, 2, 2, 2, 1\]
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 \(\Delta,\Delta-1\) is small compared to \(\Delta\) (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.
\[\begin{split}2,1,1,0,0\xrightarrow{Extension} {\bf 3}, (2+1), (1+1), (1+1), 0, 0 = 3, 3, 2, 2, 0, 0 \xrightarrow{Reduction} 2, 1, 1, 0, 0\\ 2,1,1,0,0\xrightarrow{Extension} {\bf 3}, (2+1), (1+1), 1, (0+1), 0 = 3, 3, 2, 1, 1, 0 \xrightarrow{Reduction} 2, 1, 1, 0, 0\\ 2,1,1,0,0\xrightarrow{Extension} {\bf 3}, (2+1), 1, 1, (0+1), (0+1) = 3, 3, 1, 1, 1, 1 \xrightarrow{Reduction} 2, 1, 1, 0, 0\\ ...\end{split}\]In order to extend a current degree sequence while strictly increasing its maximum degree, it is equivalent to pick a set \(I\) of elements of the degree sequence with \(|I|>\Delta\) in such a way that the \((d_i+1)_{i\in I}\) are the \(|I|\) maximum elements of the sequence \((d_i+\genfrac{}{}{0pt}{}{1\text{ if }i\in I}{0\text{ if }i\not \in I})_{1\leq i \leq n}\), and to add to this new sequence an element of value \(|I|\). The non-increasing sequence containing the elements \(|I|\) and \((d_i+\genfrac{}{}{0pt}{}{1\text{ if }i\in I}{0\text{ if }i\not \in I})_{1\leq i \leq n}\) can be reduced to \((d_i)_{1\leq i \leq n}\) by Havel and Hakimi’s rule.
\[... 1, 1, 2, {\bf 2}, {\bf 2}, 2, 2, 3, 3, \underline{3}, {\bf 3}, {\bf 3}, {\bf 4}, {\bf 6}, ... \xrightarrow{Extension} ... 1, 1, 2, 2, 2, 3, 3, \underline{3}, {\bf 3}, {\bf 3}, {\bf 4}, {\bf 4}, {\bf 5}, {\bf 7}, ...\]The number of possible sets \(I\) having this property (i.e. the number of possible extensions of a sequence) is smaller than it seems. Indeed, by definition, if \(j\not \in I\) then for all \(i\in I\) the inequality \(d_j\leq d_i+1\) holds. Hence, each set \(I\) is entirely determined by the largest element \(d_k\) of the sequence that it does not contain (hence \(I\) contains \(\{1,...,k-1\}\)), and by the cardinalities of \(\{i\in I:d_i= d_k\}\) and \(\{i\in I:d_i= d_k-1\}\).
\[I = \{i \in I : d_i= d_k \} \cup \{i \in I : d_i= d_k-1 \} \cup \{i : d_i> d_k \}.\]The number of possible extensions is hence at most cubic, and is easily enumerated.
About the implementation#
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 \(n\), Sage first
allocates an array seq
of \(n+1\) 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 \(n\) 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 (slightly) harder to enumerate all the sets
\(I\) corresponding to possible extensions of the partial sequence. As said
previously, to each set \(I\) one can associate an integer current_box
such
that \(I\) contains all the \(i\) satisfying \(d_i>current\_box\). The variable
taken
represents the number of all such elements \(i\), so that when
enumerating all possible sets \(I\) in the algorithm we have the equality
REFERENCES:
AUTHORS:
Nathann Cohen
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 \(n\).
This should be changed. Updating the code does not require more than a couple of minutes.
- class sage.combinat.degree_sequences.DegreeSequences(n)#
Bases:
object
Degree Sequences
An instance of this class represents the degree sequences of graphs on a given number \(n\) 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.EXAMPLES:
sage: DegreeSequences(8) Degree sequences on 8 elements sage: [3,3,2,2,2,2,2,2] in DegreeSequences(8) True