On the perfect one-factorization conjecture (Q1196999)

From MaRDI portal
scientific article
Language Label Description Also known as
English
On the perfect one-factorization conjecture
scientific article

    Statements

    On the perfect one-factorization conjecture (English)
    0 references
    0 references
    16 January 1993
    0 references
    For even \(n\), let \(c(n)\) denote the maximum over all one-factorizations \(\mathcal F\) of \(K_ n\) of the number of Hamilton cycles obtained by taking pairwise unions of members of \(\mathcal F\). The perfect one-factorization conjecture is that \(c(n)={n-1\choose 2}\) for even \(n\geq 4\). We show that \(c(n)\geq (n-1)\cdot\varphi(n-1)/2\) and give a multiplicative construction which shows that \(c(mn+1)\geq 2\cdot c(m+1)\cdot c(n+1)\) when \(m\) and \(n\) are odd and relatively prime. Combined with known results this occasionally improves on the first inequality.
    0 references
    Hamilton cycles
    0 references
    perfect one-factorization conjecture
    0 references

    Identifiers