dfactors

In graph theory, a dfactor (plural dfactors) refers to a d-factor: a spanning subgraph in which every vertex has degree exactly d. Given a simple graph G=(V,E) and a fixed integer d with 0 ≤ d ≤ |V|−1, a d-factor of G is a spanning subgraph H=(V,E') where E' ⊆ E and deg_H(v)=d for all v ∈ V.

More generally, an f-factor uses a function f: V → N0 specifying the target degree for each vertex; a d-factor is the special case with f(v)=d for all v. Thus dfactors are a subset of the broader f-factor framework.

Examples include: a 1-factor, which is a perfect matching; a 2-factor, which is a spanning subgraph consisting of disjoint cycles covering all vertices; and higher d-factors, where every vertex has degree d in the subgraph.

Existence and computation: The existence of an f-factor is characterized by Tutte’s f-factor theorem, which provides necessary and sufficient conditions. For fixed d, algorithms based on matching theory decide the existence of a d-factor in polynomial time. Note that if the original graph G is already d-regular, then G itself is a d-factor of G.

Special cases and results: Petersen’s theorem states that every bridgeless cubic graph (3-regular) has a 1-factor. More generally, every k-regular bipartite graph has a perfect matching (a 1-factor). These results illustrate how regularity and connectivity influence factor existence.

Applications: dfactors arise in network design, scheduling, and combinatorial design, where uniform degree constraints help ensure balanced coverage and redundancy.

See also: f-factor; perfect matching; factorization.