The reviewed record of science sign in
Pith

arxiv: 1811.06389 · v1 · pith:M7V3WFWS · submitted 2018-11-15 · math.CO

Semi-perfect 1-Factorizations of the Hypercube

Reviewed by Pith T0 review T1 audit T2 compute T3 formal T4 kernel pith:M7V3WFWSrecord.jsonopen to challenge →

classification math.CO
keywords factorizationsemi-perfectfactorizationsperfecttherecalledcyclefactors
0
0 comments X
read the original abstract

A 1-factorization $\mathcal{M} = \{M_1,M_2,\ldots,M_n\}$ of a graph $G$ is called perfect if the union of any pair of 1-factors $M_i, M_j$ with $i \ne j$ is a Hamilton cycle. It is called $k$-semi-perfect if the union of any pair of 1-factors $M_i, M_j$ with $1 \le i \le k$ and $k+1 \le j \le n$ is a Hamilton cycle. We consider 1-factorizations of the discrete cube $Q_d$. There is no perfect 1-factorization of $Q_d$, but it was previously shown that there is a 1-semi-perfect 1-factorization of $Q_d$ for all $d$. Our main result is to prove that there is a $k$-semi-perfect 1-factorization of $Q_d$ for all $k$ and all $d$, except for one possible exception when $k=3$ and $d=6$. This is, in some sense, best possible. We conclude with some questions concerning other generalisations of perfect 1-factorizations.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.