Construction Techniques for Linear Realizations of Multisets with Small Support
Аннотация
A Hamiltonian path in the complete graph $K_{v}$ whose vertices are labeled with the integers $0,1,\ldots ,v-1$ is a linear realization for the multiset $L$ of the linear edge-lengths, given by $|x-y|$ for the edge between vertices $x$ and $y$, of the edges in the path. A linear realization is standard if an end-point is 0 and perfect if the end-points are 0 and $v-1$. Linear realizations are useful in the study of the Buratti-Horak-Rosa Conjecture on the existence of cyclic realizations , where cyclic edge-lengths are given by distance modulo $v$, for given multisets. In this paper, we focus on multisets of the form $\{1^{a}, (y-k)^{b}, y^{c}\}$. Using core perfect linear realizations for supports of size 2 (which have the forms $\{x^{y-1},y^{x+1}\}$ whenever $\gcd (x,y)=1$), we construct standard linear realizations (with $a=k-1$, $b=j(y-k)$, $c=jy$) when $k\mid y$ or $k \leq 4$. When $k=2$, these allow us to show that there is a linear realization whenever $a \geq y$. This is in line with the known results for the case of $k=1$. We also supplement these results for $k=1$ by constructing linear realizations whenever $b+c < y$ and $a \geq y - \min (b,c)$, from which the coprime version of the conjecture, which requires that $v$ is coprime with each element of the multiset, follows for $k=1$ when $y \leq 16$. Our methods show promise for constructing linear realizations for arbitrary $k$, in the direction of a resolution of the conjecture for supports of size 3.