# Near $1$-factors with prescribed edge-lengths in the complete graph

###
Anita Pasotti

Università degli Studi di Brescia

####
Marco A. Pellegrini

Università Cattolica del Sacro Cuore

PDF

**Minisymposium:**
GENERAL SESSION TALKS

**Content:**
Let $K_v$ be the complete graph with vertex-set $\{0,1,\ldots,v-1\}$. The length of any edge $[x,y]$ of $K_v$ is defined by $d(x,y)=min(|x-y|,v-|x-y|)$. In 2007 Buratti conjectured that if $v$ is a prime, then
there exists a Hamiltonian path of $K_v$ whose list of edge-lengths is
ANY prescribed multiset $L$ of $v-1$ integers in $\{1,2,\ldots,\lfloor\frac{v}{2}\rfloor\}$. Partial results about this conjecture can be found in [1-5].
Recently, Meszka proposed the following similar conjecture: ``If $v$ is an odd prime, then there exists a near $1$-factor of $K_v$ whose list of edge-lengths is ANY prescribed multiset $L$ of $\frac{v-1}{2}$ integers in $\{1,2,\ldots,\lfloor\frac{v}{2}\rfloor\}$''. Rosa [7] proved that the conjecture is true when the elements of the list are $\{1,2,3\}$ or
$\{1,2,3,4\}$ or $\{1,2,3,4,5\}$. Also he proved that the conjecture is true when the list $L$ contains a ``sufficient'' number of $1$'s.
In this talk we propose a generalization of this problem
to the case in which $v$ is an odd integer not necessarily prime [6]. In particular, we give a necessary condition for the existence of such a near $1$-factor and we conjecture that such a condition is also sufficient. If $v$ is a prime our conjecture reduces to Meszka's one.
Then we show that our conjecture is true for any list $L$ whose underlying set $S$ has size $1$, $2$, or $\lfloor\frac{v}{2}\rfloor$,
or when $S=\{1,2,t\}$ for any positive integer $t$ not coprime with $v$.
Also, we give partial results when $t$ and $v$ are coprime. Finally, we present a complete solution for $t\leq 11$.
\vspace{5mm}
\noindent{\bf References:}
\begin{itemize}
\item[{[1]}] Capparelli S., Del Fra A.,
Hamiltonian paths in the complete graph with edge-lengths $1,2,3$,
Electron. J. Combin. 17 (2010), $\sharp$R44.
\item[{[2]}] Dinitz J.H., Janiszewski S.R.,
On hamiltonian paths with prescribed edge lengths in the complete graph,
Bull. Inst. Combin. Appl. 57 (2009), 42--52.
\item[{[3]}] Horak P., Rosa A.,
On a problem of Marco Buratti,
Electron. J. Combin. 16 (2009), $\sharp$R20.
\item[{[4]}] Pasotti A., Pellegrini M.A., A new result on the problem of Buratti, Horak and Rosa, Discrete Math. 319 (2014), 1--14.
\item[{[5]}] Pasotti A., Pellegrini M.A.,
On the Buratti-Horak-Rosa conjecture about Hamiltonian paths in complete graphs,
Electron. J. Combi. 21 (2014), $\sharp$P2.30.
\item[{[6]}] Pasotti A., Pellegrini M.A., A generalization of the problem of Mariusz Meszka,
published online on Graphs Combin., doi: 10.1007/s00373-015-1563-0.
\item[{[7]}] Rosa A., On a problem of Mariusz Meszka, Discrete Math. 338 (2015), 139--143.
\end{itemize}