A graph factor is a spanning subgraph. An -factor is a regular graph of vertex degree that spans the original graph. In particular, a 2-factor of a finite graph that is a simple graph is a disjoint union of cycle graphs covering all vertices.

A 1-factor of a graph with graph vertices is a set of separate graph edges which collectively contain all of the graph vertices of among their endpoints. Harary and Palmer (1973, p. 270) list the enumeration of 1-factors and factorizations as graphical enumeration problems.

A one-factorization partitions the edge set of a graph into perfect matchings. It is a perfect one-factorization when every two distinct factors together form a Hamiltonian cycle (Gill and Wanless 2020, p. 177).

See also

2-Factor, 2-Factorization, Graph

Explore with Wolfram|Alpha

References

Gill, M. J. and Wanless, I. M. "Perfect 1-Factorisations of ." Bull. Austral. Math. Soc. 101, 177-185, 2020. https://doi.org/10.1017/S0004972719000856.Harary, F. and Palmer, E. M. "A Survey of Graphical Enumeration Problems." In A Survey of Combinatorial Theory (Ed. J. N. Srivastava). Amsterdam, Netherlands: North-Holland, pp. 259-275, 1973.

Referenced on Wolfram|Alpha

Graph Factor

Cite this as:

Weisstein, Eric W. "Graph Factor." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/GraphFactor.html

Subject classifications