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
    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
    0 references

    Identifiers