NetworkX

Previous topic

is_valid_degree_sequence_havel_hakimi

Next topic

Isolates

is_valid_degree_sequence_erdos_gallai

is_valid_degree_sequence_erdos_gallai(deg_sequence)[source]

Returns True if deg_sequence is a valid degree sequence.

A degree sequence is valid if some graph can realize it. Validation proceeds via the Erdős-Gallai algorithm.

Worst-case run time is: O( n**2 )

Parameters :

deg_sequence : list

A list of integers where each element specifies the degree of a node in a graph.

Returns :

valid : bool

True if deg_sequence is a valid degree sequence and False if not.

References

[EG1960], [choudum1986]