Originator: Marco Buratti (communicated by Jeff Dinitz - presented at REGS 2008)
Background: Given a prime p, we seek a spanning path in Kp using edges of specified lengths. Viewing the vertex set as the set of congruence classes mod p, the length of an edge xy is defined to be either |x-y| or p-|x-y|, whichever is needed.
Conjecture: If S is a multiset consisting of p-1 nonzero congruence classes mod p, then Kp has a spanning path using edges whose lengths are the elements of S.
Comments: A few special cases are easy. If S consists of p-1 copies of the same length, then the primality of p makes the construction trivial. If S consists of one copy of each length, then a "zig-zag" path has the desired property. This is a path with successive edge-lengths (1,-2,3,-4,...); note that length -2 is the same as length 2.
Dinitz and Janiszewski [DJ] proved the conjecture in the case where S has two distinct lengths. Using multiplication by a constant to permute the vertices (since p is prime), it suffices to assume that the lengths are 1 and k, which more copies of 1 than k. The proof is then completed by giving constructions in several cases.
Horak and Rosa [HR] discuss several equivalent graph problems. Meszka checked the conjecture by computer up to p=23.
It is always easy to build a spanning tree in Kp using edges of specified lengths. One could seek a partial result toward the problem by showing that r leaves always suffice, for some r (possibly as a function of p). The full conjecture is the statement that there is always such a tree with only two leaves.
References:
[DJ] J.H. Dinitz and S.R. Janiszewski;
On Hamiltonian paths in the complete graph with prescribed edge lengths.
[HR] P. Horak and A. Rosa;
On a problem of Marco Buratti.