Hamiltonian Paths in the Complete Graph with Edge-Lengths 1, 2, 3

  • Stefano Capparelli
  • Alberto Del Fra


Marco Buratti has conjectured that, given an odd prime $p$ and a multiset $L$ containing $p-1$ integers taken from $\{1,\ldots,(p-1)/2\}$, there exists a Hamiltonian path in the complete graph with $p$ vertices whose multiset of edge-lengths is equal to $L$ modulo $p$. We give a positive answer to this conjecture in the case of multisets of the type $\{1^a,2^b,3^c\}$ by completely classifying such multisets that are linearly or cyclically realizable.

Article Number