networkx.generators.degree_seq.havel_hakimi_graph

havel_hakimi_graph(deg_sequence, create_using=None)

Return a simple graph with given degree sequence, constructed using the Havel-Hakimi algorithm.

Parameters:

deg_sequence: list of integers :

Each integer corresponds to the degree of a node (need not be sorted).

create_using : graph, optional (default Graph)

Return graph of this type. The instance will be cleared. Multigraphs and directed graphs are not allowed.

Raises:

NetworkXException :

For a non-graphical degree sequence (i.e. one not realizable by some simple graph).

Notes

The Havel-Hakimi algorithm constructs a simple graph by successively connecting the node of highest degree to other nodes of highest degree, resorting remaining nodes by degree, and repeating the process. The resulting graph has a high degree-associativity. Nodes are labeled 1,.., len(deg_sequence), corresponding to their position in deg_sequence.

See Theorem 1.4 in [chartrand-graphs-1996]. This algorithm is also used in the function is_valid_degree_sequence.

References

[R54]

G. Chartrand and L. Lesniak, “Graphs and Digraphs”, Chapman and Hall/CRC, 1996.