2015/04/28 by Francesca Merola, Merola, Francesca, Anita Pasotti +3
Biochemistry, Genetics and Molecular Biology · Computer Science · Engineering · Mathematics · #05B30 #14-3-3 protein interactions #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems #Limits and Structures in Graph Theory #graph theory and CDMA systems #math.CO #msc:05B30
paper · pdf · doi:10.48550/arxiv.1504.07369
14 pages
arxiv created 2015/04/28 · openalex publication_date 2015/04/28 · arxiv updated 2015/04/29 · openalex created_date 2022/09/03 · openalex updated_date 2026/07/28
A hamiltonian cycle system (HCS, for short) of a graph Γ is a partition of the edges of Γ into hamiltonian cycles. A HCS is cyclic when it is invariant under a cyclic permutation of all the vertices of Γ; the existence problem for a cyclic HCS has been completely solved by Buratti and Del Fra in 2004 when Γ is the complete graph Kv, v odd, and by Jordon and Morris in 2008 when Γ is the complete graph minus a 1-factor Kv-I, v even. In this work we present a complete solution to the existence problem of a cyclic HCS for Γ= Km× n, the complete multipartite graph, when the number of parts m is even. We also give necessary and sufficient conditions for the existence of a cyclic and symmetric HCS of Γ; the notion of a symmetric HCS of a graph Γ has been introduced in 2004 by Akiyama, Kobayashi, and Nakamura for Γ=Kv, v odd, in 2011 by Brualdi and Schroeder when Γ= Kv-I, v even, and, very recently, by Schroeder when Γ is the complete multipartite graph.