A degree sequence is an ordered list of degrees for the vertices of a graph. For example, here are some graphs and their degree sequences:
Clearly, each graph has only one degree sequence, but the reverse is not true - one degree sequence can correspond to many graphs. Finally, an ordered sequence of numbers (d1 >= d2 >= ... >= dn > 0) may not be the degree sequence of a graph - in other words, it is not graphical.
The Havel-Hakimi (HH) theorem gives us a way to test a degree sequence to see if it is graphical or not. As a side-effect, a graph is produced that realises the sequence. Note that it only produces one graph, not all of them. It proceeds by attaching the first vertex of highest degree to the next set of high-degree vertices. If there are none left to attach to, it has either used up all the sequence to produce a graph, or the sequence was not graphical.
The image above shows the HH algorithm at work on the sequence [3, 3, 2, 2, 1, 1]. Unfortunately, this produces none of the nice connected examples in the lower part of the first image, because all the connections are used up by the first four vertices, leaving a 1-1 pair.
Luckily there is this paper by Kim, Toroczkai, Miklós, Erdős, and Székely (Péter Erdős, not Paul) on a 'Generalized' version. It proves that a sequence is graphical if the sequence reduced by an adjacency set of a vertex is also graphical. To be honest, this is not hugely helpful for making a more general algorithm (to me, at least).
However, a fusion of the 'saturating' algorithm of Faulon's third signature paper and the theorem of Kim et al does seem to work. The idea is to try all combinations of possible adjacency sets (connections) and test each of these for being graphical. Each vertex i is 'saturated' in turn by making d[i] edges to other vertices with a degree greater than 0.
The problem with this simple procedure is that it makes many isomorphic graphs (as usual!). It seems possible that there is a way to avoid some of this redundancy, but I'm not sure if can all be avoided easily.
Clearly, each graph has only one degree sequence, but the reverse is not true - one degree sequence can correspond to many graphs. Finally, an ordered sequence of numbers (d1 >= d2 >= ... >= dn > 0) may not be the degree sequence of a graph - in other words, it is not graphical.
The Havel-Hakimi (HH) theorem gives us a way to test a degree sequence to see if it is graphical or not. As a side-effect, a graph is produced that realises the sequence. Note that it only produces one graph, not all of them. It proceeds by attaching the first vertex of highest degree to the next set of high-degree vertices. If there are none left to attach to, it has either used up all the sequence to produce a graph, or the sequence was not graphical.
The image above shows the HH algorithm at work on the sequence [3, 3, 2, 2, 1, 1]. Unfortunately, this produces none of the nice connected examples in the lower part of the first image, because all the connections are used up by the first four vertices, leaving a 1-1 pair.
Luckily there is this paper by Kim, Toroczkai, Miklós, Erdős, and Székely (Péter Erdős, not Paul) on a 'Generalized' version. It proves that a sequence is graphical if the sequence reduced by an adjacency set of a vertex is also graphical. To be honest, this is not hugely helpful for making a more general algorithm (to me, at least).
However, a fusion of the 'saturating' algorithm of Faulon's third signature paper and the theorem of Kim et al does seem to work. The idea is to try all combinations of possible adjacency sets (connections) and test each of these for being graphical. Each vertex i is 'saturated' in turn by making d[i] edges to other vertices with a degree greater than 0.
The problem with this simple procedure is that it makes many isomorphic graphs (as usual!). It seems possible that there is a way to avoid some of this redundancy, but I'm not sure if can all be avoided easily.
Comments