A Quantitative Approach to Perfect One-Factorizations of Complete Bipartite Graphs

Abstract

Given a one-factorization $\mathcal{F}$ of the complete bipartite graph $K_{n,n}$, let ${\sf pf}(\mathcal{F})$ denote the number of Hamiltonian cycles obtained by taking pairwise unions of perfect matchings in $\mathcal{F}$. Let ${\sf pf}(n)$ be the maximum of ${\sf pf}(\mathcal{F})$ over all one-factorizations $\mathcal{F}$ of $K_{n,n}$. In this work we prove that ${\sf pf}(n)\geq n^2/4$, for all $n\geq 2$.