TOPICS
Search

Perfect One-Factorization


A perfect one-factorization of a finite simple graph is a one-factorization such that the union of any two distinct factors is a Hamiltonian cycle (Gill and Wanless 2020, p. 177). For a positive integer n, a one-factorization of the complete graph K_(2n) consists of 2n-1 perfect matchings. An isomorphism between two such factorizations is a permutation of the vertices that carries the collection of factors of one to the collection of factors of the other.

Ivanov and Tertitski (2026, Theorem 1) report exactly 10,710 perfect one-factorizations, counted up to isomorphism, of K_(18) having a nontrivial automorphism group. Of these, 531 have automorphism group of group order greater than 2 and 10,179 have automorphism group of group order 2. This is a count restricted to factorizations with nontrivial automorphisms, not a count of all perfect one-factorizations of K_(18). The authors used AI assistants to write and optimize parts of the enumeration software and checked the results. The exhaustive enumeration has not been independently repeated here.


See also

Complete Graph, Hamiltonian Cycle, One-Factorization, Perfect Matching

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.Ivanov, A. V. and Tertitski, L. M. "Perfect 1-Factorisations of K_(18) with a Non-Trivial Automorphism Group." 1 Nov 2026. https://arxiv.org/abs/2611.01807v1.Wallis, W. D. One-Factorizations. Dordrecht, Netherlands: Kluwer, 1997. https://doi.org/10.1007/978-1-4757-2564-3.

Cite this as:

Weisstein, Eric W. "Perfect One-Factorization." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/PerfectOne-Factorization.html

Subject classifications