Is there software to reconstruct a graph from its degree sequence? [closed]

$\begingroup$

I use Mathematica but it does not have a function to reconstruct a graph from its degree sequence. eg : (5,1,1,1,1,1).

Is there a software that does this?

$\endgroup$ 4

3 Answers

$\begingroup$

This is not simple, in general. There are $19$ different graphs represented by the degree sequence $(3,3,3,3,3,3,3,3,3,3)$ (cubic graphs with $10$ nodes), shown here.

You might be interested in the answer I got to my question on graphs with the degree sequence $(5,4,3,2,2,2,1,1,1,1,1,1,1,1)$, which represents a tree, but still had - as it turns out - $150$ different options. The answer describes the software used.

Some degree sequences are easy, of course. As others have noted your example is just a star:

$\endgroup$ $\begingroup$

An integer sequence $(n_1,\ldots,n_k)$ is called realizable if there is a graph $G = (V,E)$ with vertex set $V = \{ v_1,\ldots,v_k\}$ such that such $deg(v_i) = n_i$ for all $ i \in [1,n]$.

However, there can be more than one graph with a given degree sequence, and conversely there are integer sequences that do not correspond to the degree sequence of any graph.

See for a short overview of results.

In 1962 Hakimi showed that there is a polynomial-time algorithm for checking if an integer sequence is realizable. The same result was actually established already in 1955 by Havel, but unfortunately the paper was only published in Czech.

Later it has been shown that some other problems concerning degree sequences are in fact NP-complete. See .

$\endgroup$ $\begingroup$

Here is a link to someone who has answered something similar. If you can code, this is useful.Constructing a graph from a degree sequence

$\endgroup$