TOPICS
Search

Graph Factor


A graph factor is a spanning subgraph. An r-factor is a regular graph of vertex degree r 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 G with n graph vertices is a set of n/2 separate graph edges which collectively contain all n of the graph vertices of G 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 K_(16)." 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