Escalera de Möbius

En teoría de grafos, la escalera de Möbius , para números  pares, se forma a partir de un  agregando aristas (llamadas "peldaños") que conectan pares opuestos de vértices en el ciclo. Es un grafo cúbico y circulante, llamado así porque, con la excepción de  (el problema de los tres servicios ),  tiene exactamente  4-ciclos, que se unen por sus aristas compartidas para formar una banda de Möbius topológica. Las escaleras de Möbius fueron nombradas y estudiadas por primera vez por .

Propiedades
Para cada  par, la escalera de Möbius  es un grafo de ápice no plano, lo que significa que no se puede dibujar sin cruces en el plano, pero al eliminar un vértice se puede dibujar el grafo restante sin cruces. Estos grafos tienen un número de cruces, pero se pueden incrustar sin cruces en un toro o en el plano proyectivo. Por lo tanto, son ejemplos de grafos toroidales. exploró las incrustaciones de estos grafos en superficies de género superior.

Las escaleras de Möbius son vértices-transitivas (tienen simetrías que llevan cualquier vértice a cualquier otro vértice), pero (con las excepciones de  y ) no son isotoxales. Las aristas del ciclo a partir del cual se forma la escalera se pueden distinguir de los peldaños de la escalera, porque cada arista de ciclo pertenece a un solo 4-ciclo, mientras que cada peldaño pertenece a dos de estos ciclos. Por lo tanto, no hay simetría al llevar una arista de ciclo a una arista de peldaño o viceversa.

Cuando n =  2 (mod 4), Mn es bipartito. Cuando n = 0 (mod 4), no es bipartito. Los puntos finales de cada peldaño están separados por una distancia uniforme en el ciclo inicial, por lo que agregar cada peldaño crea un ciclo impar.

En este caso, debido a que el grafo es 3-regular pero no bipartito, por el teorema de Brooks se puede afirmar que posee coloración 3. demostró que las escaleras de Möbius están determinadas únicamente por sus polinomios de Tutte.

La escalera de Möbius M8 tiene 392 árboles de expansión. Esta escalera y M6 tienen la mayor cantidad de árboles de expansión entre todos los grafos cúbicos con el mismo número de vértices. Sin embargo, el grafo cúbico de 10 vértices con más árboles de expansión es el grafo de Petersen, que no es una escalera de Möbius.

Los polinomios de Tutte de las escaleras de Möbius pueden calcularse mediante una simple relación de recurrencia.

Grafos menores

Las escaleras de Möbius juegan un papel importante en la teoría de grafos menores. El primer resultado de este tipo es un teorema de  según el que se pueden formar grafos sin el menor K5 mediante el uso de operaciones de suma de cliques para combinar grafos planos y la escalera de Möbius M8; por esta razón M8 se llama grafo de Wagner. definió un grafo casi plano como un grafo no plano para el que todo menor no trivial es plano. También demostró que los grafos casi planos 3-conectados son escaleras de Möbius o miembros de un pequeño número de otras familias, y que se pueden formar otros grafos casi planos a partir de estos mediante una secuencia de operaciones simples. demostró que casi todos los grafos que no tienen un menor cúbico pueden generarse mediante una secuencia de operaciones simples sobre las escaleras de Möbius.

Química y física

 sintetizó por primera vez estructuras moleculares en forma de escalera de Möbius, y desde entonces esta estructura ha sido de interés en química y estereografía química, especialmente en vista de la forma de escalera de las moléculas de ADN. Con esta aplicación en mente, estudió las simetrías matemáticas de los embebidos de las escaleras de Möbius en R3. En particular, como muestra, cada inserción tridimensional de una escalera de Möbius con un número impar de peldaños es topológicamente quiral: no puede convertirse en su imagen especular mediante una deformación continua del espacio sin pasar un borde por otro. Por otro lado, las escaleras de Möbius con un número par de peldaños tienen embebidos en R3 que pueden deformarse para obtener sus imágenes especulares.

Igualmente, se han utilizado como la forma de un anillo superconductor en experimentos para estudiar los efectos de la topología del conductor en las interacciones de los electrones.

Optimización combinatoria

Las escaleras de Möbius también se han utilizado en ciencias de la computación, como parte de los enfoques de programación en enteros para problemas de empaquetamiento de conjuntos y ordenamiento lineal. Ciertas configuraciones dentro de estos problemas se pueden usar para definir facetas del politopo que describen una relajación en la programación lineal del problema; estas facetas se denominan restricciones de escalera de Möbius.

Véase también
 Grafo de Ladder
 Grafo prisma

Referencias

Bibliografía

Enlaces externos
 

Familias paramétricas de grafos
Grafos regulares