Consider the complete graph Kv. Label the vertices with the distinct elements of Zv, the

cyclic group of order v. Label each edge with the cyclical distance between its end-vertices. Accordingly, each path in Kv is associated with a multiset of such edge labels. The Buratti-Horak-Rosa(BHR) conjecture, initially proposed in 2007 and reformulated several times, asks the reverse question for Hamiltonian paths through Kv. This has certain implications for graph decompositions,which, in return, have applications in computer science, including partitioning networks for structural analysis.

In more precise terms, a Hamiltonian path through Kv is called a realization of a multiset L of
size v − 1 if its edge labels are L. The BHR conjecture is that there is a realization for a multiset L if and only if, for any divisor dd of v, the number of multiples of d in L is at most v − d. It has been shown early on that the conjecture holds for multisets of support at most 2. However, only partial results have been achieved so far for other supports.
We observe that a toroidal lattice of vertices is associated with a given multiset. This allows us
to construct certain useful types of realizations as building blocks [1, 2, 3]. Our current focus is

mainly on multisets with support of size 3, where certain relevant lattices are cylindrical. The ongoing expansion of our constructions is considerably extending the parameters for which the conjecture is known to hold.

References:

[1] O. Ağırseven and M. A. Ollis, Grid-based graphs, linear realizations and the Buratti-Horak-
Rosa conjecture, submitted, arXiv:2402.08736.

[2] O. Ağırseven and M. A. Ollis, A coprime Buratti-Horak-Rosa conjecture and grid-based lin-
ear realizations, submitted, arXiv:2412.05750.

[3] O. Ağırseven and M. A. Ollis, Construction techniques for linear realizations of multisets with
small support, submitted, arXiv:2502.00164.