Tuyển tập các báo cáo nghiên cứu khoa học trên tạp chí toán học quốc tế đề tài: Sequentially perfect and uniform one-factorizations of the complete graph. | Sequentially perfect and uniform one-factorizations of the complete graph Jeffrey H. Dinitz Mathematics and Statistics University of Vermont Burlington VT USA 05405 Peter Dukes Mathematics and Statistics University of Victoria Victoria BC Canada V8W 3P4 dukes@ Douglas R. Stinson School of Computer Science University of Waterloo Waterloo ON Canada N2L 3G1 dstinson@ Submitted Aug 23 2004 Accepted Oct 12 2004 Published Jan 7 2005 Mathematics Subject Classifications 05C70 Abstract 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 K2n 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 1 that there is a sequentially perfect one-factorization of K2n. As well for any odd integer m 1 we prove that there is a sequentially uniform one-factorization of K2tm of type 4 4 . . . 4 for all integers t 2 log2 m where type 4 4 . . . 4 denotes a two-regular graph consisting of disjoint cycles of length four . 1 Introduction A one-factor of a graph G is a subset of its edges which partitions the vertex set. A one-factorization of a graph G is a partition of its edges into one-factors. Any one-factorization THE ELECTRONIC JOURNAL OF COMBINATORICS 12 2005 R1 1 of the complete graph K2n has 2n 1 one-factors each of which has n edges. For a survey of one-factorizations of the complete graph the reader is referred to 10 14 or 15 . A one-factorization Fo . F2n-2 of K2n is sequentially uniform if the one-factors
