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}

Back to all abstracts