On perfect one-factorization of the complete graph \(K_{2p}\) (Q920115)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On perfect one-factorization of the complete graph \(K_{2p}\) |
scientific article |
Statements
On perfect one-factorization of the complete graph \(K_{2p}\) (English)
0 references
1989
0 references
Let \(K_{2n}=(V,E)\) denote the complete graph of order 2n and size n(2n- 1). A 1-factor of \(K_{2n}\) is a set of pairwise disjoint edges that covers all the vertices in V. A 1-factorization of \(K_{2n}\) is a set of 1-factors that partition the set of edges E. A 1-factorization is called perfect if the union of every pair of distinct 1-factors is a Hamiltonian circuit. Two 1-factorizations F and \(F'\) are isomorphic if there exists a permutation of V which sends each member of F into a member of \(F'.\) It is conjectured that a perfect 1-factorization of \(K_{2n}\) exists for all n, but it is not known whether a perfect 1-factorization of \(K_{2n}\) exists except for n a prime, 2n-1 a prime, and several other orders [see \textit{J. H. Dinitz} and \textit{D. R. Stinson}, Some new perfect 1-factorizations from starters in finite fields, J. Graph Theory 13, No.4, 405-415 (1989; Zbl 0678.05044), Institute for Mathematics and its Applications, University of Minnesota, IMA Preprint Series {\#} 450]. It is now known, up to isomorphism, how many different perfect 1- factorizations of \(K_{2n}\) there are. In [Finite topologies and Hamilton path, J. Comb. Theory, Ser. B 14, 87- 93 (1973; Zbl 0249.54002), and Symmetry groups of some perfect 1- factorizations of complete graphs, Discrete Math. 18, 227-234 (1977; Zbl 0383.05032)] \textit{B. A. Anderson} constructed a perfect 1-factorization \(GA_{2p}\) of \(K_{2p}\), if p is an odd prime. In [Dudney's round table problem and the edge-coloring of the complete graph (in Japanese), Sugaku Seminar No.159, 24-29 (1975)] \textit{Nakamura} also constructed a perfect 1-factorization \(GN_{2p}\) of \(K_{2p}\) in a different way. The author proves that \(GA_{2p}\) and \(GN_{2p}\) are isomorphic.
0 references
perfect factorization
0 references
1-factorization
0 references
Hamiltonian circuit
0 references