networkx.generators.degree_seq.havel_hakimi_graph¶

havel_hakimi_graph
(deg_sequence, create_using=None)[source]¶ Returns a simple graph with given degree sequence constructed using the HavelHakimi algorithm.
Parameters:  deg_sequence (list of integers) – Each integer corresponds to the degree of a node (need not be sorted).
 create_using (NetworkX graph constructor, optional (default=nx.Graph)) – Graph type to create. If graph instance, then cleared before populated. Directed graphs are not allowed.
Raises: NetworkXException
– For a nongraphical degree sequence (i.e. one not realizable by some simple graph).Notes
The HavelHakimi 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 degreeassociativity. Nodes are labeled 1,.., len(deg_sequence), corresponding to their position in deg_sequence.
The basic algorithm is from Hakimi [1] and was generalized by Kleitman and Wang [2].
References
[1] Hakimi S., On Realizability of a Set of Integers as Degrees of the Vertices of a Linear Graph. I, Journal of SIAM, 10(3), pp. 496506 (1962) [2] Kleitman D.J. and Wang D.L. Algorithms for Constructing Graphs and Digraphs with Given Valences and Factors Discrete Mathematics, 6(1), pp. 7988 (1973)