Sequentially perfect and uniform one-factorizations of the complete graph

Jeffrey H. Dinitz ; Peter Dukes ; Douglas R. Stinson

The electronic journal of combinatorics, Tome 12 (2005)

Résumé

In this paper, we consider a weakening of the definitions of uniform and perfect one-factorizations of the complete graph. Basically, we want to order the $2n-1$ one-factors of a one-factorization of the complete graph $K_{2n}$ in such a way that the union of any two (cyclically) consecutive one-factors is always isomorphic to the same two-regular graph. This property is termed sequentially uniform; if this two-regular graph is a Hamiltonian cycle, then the property is termed sequentially perfect. We will discuss several methods for constructing sequentially uniform and sequentially perfect one-factorizations. In particular, we prove for any integer $n \geq 1$ that there is a sequentially perfect one-factorization of $K_{2n}$. As well, for any odd integer $m \geq 1$, we prove that there is a sequentially uniform one-factorization of $K_{2^t m}$ of type $(4,4,\dots,4)$ for all integers $t \geq 2 + \lceil \log_2 m \rceil$ (where type $(4,4,\dots,4)$ denotes a two-regular graph consisting of disjoint cycles of length four).

Détail

DOI : 10.37236/1898

Classification : 05C70