2013/05/28 by Anita Pasotti, Pasotti, Anita, Marco Antonio Pellegrini +1 · 1 citation
Computer Science · Engineering · Mathematics · #05C38 #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems #Limits and Structures in Graph Theory #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.1305.6482
openalex publication_date 2013/05/28 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The conjecture of Peter Horak and Alex Rosa (generalizing that of Marco Buratti) states that a multiset L of v-1 positive integers not exceeding [v/2] is the list of edge-lengths of a suitable Hamiltonian path of the complete graph with vertex-set 0,1,...,v-1 if and only if the following condition (here reformulated in a slightly easier form) is satisfied: for every divisor d of v, the number of multiples of d appearing in L is at most v-d. In this paper we do some preliminary discussions on the conjecture, including its relationship with graph decompositions. Then we prove, as main result, that the conjecture is true whenever all the elements of L are in 1,2,3,5.