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)
sage: g.degree_sequence()
[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 Erdos and Gallai:

Erdos 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\)

\[\sum_{j\leq i}d_j \leq j(j-1) + \sum_{j>i} \min(d_j,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

\[I = \text{taken }+\text{ number of elements of value }current\_box+ \text{ number of elements of value }current\_box-1.\]

REFERENCES:

[RCES1994]

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