Horak–Rosa Hamiltonian path conjecture

Let KvK_v denote the complete graph on {0,1,,v1}\{0,1,\dots,v-1\}, and let (H)\ell(H) be the multiset of edge-lengths of a graph HH, with edge lengths in KvK_v defined by (x,y)=min(xy,vxy)\ell(x,y)=\min(|x-y|,v-|x-y|). Horak–Rosa conjecture. Let LL be a list of v1v-1 positive integers not exceeding v/2\lfloor v/2\rfloor. Then there exists a Hamiltonian path HH of KvK_v such that (H)=L\ell(H)=L if and only if, for every divisor dd of vv, the number of multiples of dd appearing in LL does not exceed vdv-d. The conjecture generalizes Buratti's problem to arbitrary orders and is stated in the paper as still widely open, with partial results known.

Sources & referencesView supporting material

Primary source

Anita Pasotti and Marco Antonio Pellegrini, “A generalization of the problem of Mariusz Meszka”, arXiv:1404.3890 (2015).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.