The conjecture of Peter Horak and Alex Rosa (generalizing that of Marco Buratti) states that a multiset L of ν-1 positive integers not exceeding ⌊ν/2⌋ is the list of edge-lengths of a suitable Hamiltonian path of the complete graph with vertex-set {0,1,⋯,ν-1} if and only if the following condition (here reformulated in a slightly easier form) is satisfied: for every divisor d of ν, 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}

A new result on the problem of Buratti, Horak and Rosa

PASOTTI, Anita;
2014-01-01

Abstract

The conjecture of Peter Horak and Alex Rosa (generalizing that of Marco Buratti) states that a multiset L of ν-1 positive integers not exceeding ⌊ν/2⌋ is the list of edge-lengths of a suitable Hamiltonian path of the complete graph with vertex-set {0,1,⋯,ν-1} if and only if the following condition (here reformulated in a slightly easier form) is satisfied: for every divisor d of ν, 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}
2014
Ateneo di appartenenza
PE1_15 Discrete mathematics and combinatorics
Esperti anonimi
Inglese
Internazionale
STAMPA
319
1
1
14
14
edge-lengths; Hamiltonian path; complete graph
Altre Istituz. pubb. estere
2
info:eu-repo/semantics/article
262
Pasotti, Anita; Pellegrini, M. A.
1 Contributo su Rivista::1.1 Articolo in rivista
none
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11379/290304
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 14
  • ???jsp.display-item.citation.isi??? 13
social impact