k_factor#

k_factor(G, k, matching_weight='weight')[source]#

Compute a k-factor of a graph.

A k-factor of a graph is a spanning k-regular subgraph. A spanning k-regular subgraph of G is a subgraph that contains each node of G and a subset of the edges of G such that each node has degree k.

Parameters:

GNetworkX graph: An undirected graph.
kint: The degree of the k-factor.
matching_weight: string, optional (default=”weight”): Edge attribute name corresponding to the edge weight. If not present, the edge is assumed to have weight 1. Used for finding the max-weighted perfect matching.

Returns:

NetworkX graph: A k-factor of G.

References

[1]

“An algorithm for computing simple k-factors.”, Meijer, Henk, Yurai Núñez-Rodríguez, and David Rappaport, Information processing letters, 2009.

Examples

>>> G = nx.Graph([(1, 2), (2, 3), (3, 4), (4, 1)])
>>> KF = nx.k_factor(G, k=1)
>>> KF.edges()
EdgeView([(1, 2), (3, 4)])