is_valid_degree_sequence_erdos_gallai#

is_valid_degree_sequence_erdos_gallai(deg_sequence)[source]#

Returns True if deg_sequence can be realized by a simple graph.

The validation is done using the Erdős-Gallai theorem [EG1960].

Parameters:

deg_sequencelist: A list of integers

Returns:

validbool: True if deg_sequence is graphical and False if not.

Notes

This implementation uses an equivalent form of the Erdős-Gallai criterion. Worst-case run time is $O (n)$ where $n$ is the length of the sequence.

Specifically, a sequence d is graphical if and only if the sum of the sequence is even and for all strong indices k in the sequence,

$\sum_{i = 1}^{k} d_{i} \leq k (k - 1) + \sum_{j = k + 1}^{n} min (d_{i}, k) = k (n - 1) - (k \sum_{j = 0}^{k - 1} n_{j} - \sum_{j = 0}^{k - 1} j n_{j})$

A strong index k is any index where d_k >= k and the value n_j is the number of occurrences of j in d. The maximal strong index is called the Durfee index.

This particular rearrangement comes from the proof of Theorem 3 in [2].

The ZZ condition says that for the sequence d if

| d | >= \frac{(max (d) + min (d) + 1)^{2}}{4 * min (d)}

then d is graphical. This was shown in Theorem 6 in [2].

References

[1]

A. Tripathi and S. Vijay. “A note on a theorem of Erdős & Gallai”, Discrete Mathematics, 265, pp. 417-420 (2003).

[2] (1,2)

I.E. Zverovich and V.E. Zverovich. “Contributions to the theory of graphic sequences”, Discrete Mathematics, 105, pp. 292-303 (1992).

[EG1960]

Erdős and Gallai, Mat. Lapok 11 264, 1960.

Examples

>>> G = nx.Graph([(1, 2), (1, 3), (2, 3), (3, 4), (4, 2), (5, 1), (5, 4)])
>>> sequence = (d for _, d in G.degree())
>>> nx.is_valid_degree_sequence_erdos_gallai(sequence)
True

To test a non-valid sequence: >>> sequence_list = [d for _, d in G.degree()] >>> sequence_list[-1] += 1 >>> nx.is_valid_degree_sequence_erdos_gallai(sequence_list) False