Número máximo de ciclos de expansión sin borde común en un gráfico completo

Es posible dividir todos los bordes del gráfico completo en ciclos hamiltonianos siempre que$n$es impar. Además, es claramente imposible cuando$n$es par, ya que en ese caso el número de aristas no es un múltiplo de$n$.

Primero, divida un gráfico completo de orden par en$2m$vértices en$m$Caminos hamiltonianos , usando la construcción en esta otra respuesta . Luego, agregue un nuevo vértice y cierre cada uno de estos caminos conectando ambos extremos al nuevo vértice. Ahora tienes$m$Ciclos hamiltonianos con aristas disjuntas en el gráfico completo en$2m+1$vértices.

Obtuve esta construcción de Wikipedia , donde se atribuye a Welecki. Ellos dan la siguiente ilustración útil, por$n=9$.

La solución es fácil cuando$n=2m+1$es un primo impar: en redondo$k$,$1\le k\le m$, poner persona$i$en el asiento$ki\bmod n$(las personas y los asientos están numerados de$0$a$n-1$). Esto utiliza el número mínimo de$m=\frac{n-1}2$rondas y comprobamos que las personas$x,y$reunirse en ronda$\min\{|x-y|,n-|x-y|\}$.

Si$n$es impar, pero compuesto, el método anterior no funciona de inmediato: cuando$1<k\mid n$, intentaríamos colocar a varias personas en los mismos asientos. Podemos tratar de desentrañar esto, pero eso resulta en$\frac nk$cumple con ser reemplazado con otras distancias ... pero supongo que esto aún puede ser factible para algunos$n$(¿Quizás con algunas excepciones, como los cuadrados de los números primos? No lo intenté todo todavía)

Cuando$n$es incluso, por supuesto, ni siquiera podemos esperar lograr$\frac{n-1}2$.