On perfect one-factorization of the complete graph \(K_{2p}\)
type: Item
instance of: scholarly article
title: On perfect one-factorization of the complete graph \(K_{2p}\)
zbMATH Open document ID: 0708.05047
DOI: 10.1007/BF01788690
author: Midori Kobayashi
published in: Graphs and Combinatorics
publication date: 1989-01-01T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 05C70
zbMATH DE Number: 4162927
zbMATH Keywords: perfect factorization
zbMATH Keywords: 1-factorization
zbMATH Keywords: Hamiltonian circuit
reviewed by: Don R. Lick
MaRDI profile type: Publication
cites work: Finite topologies and Hamiltonian paths
cites work: Symmetry groups of some perfect 1-factorizations of complete graphs
description: scientific article; zbMATH DE number 4162927