TOPICS
Search

Möbius Ladder

DOWNLOAD Mathematica NotebookDownload Wolfram Notebook
MoebiusLadders

An n-Möbius ladder, sometimes called a Möbius wheel (Jakobson and Rivin 1999), is a simple graph on 2n vertices obtained by introducing a twist in an n-prism graph that is isomorphic to the circulant graph Ci_(2n)(1,n) for a positive integer n>=3. Möbius ladders are sometimes denoted M_n.

The 4-Möbius ladder is known as the Wagner graph. The (2n-1)-Möbius ladder is isomorphic to the Haar graph H(2^(2n-2)+3) for n>=2.

Möbius ladders are Hamiltonian, graceful (Gallian 1987, Gallian 2025), and by construction, singlecross. The Möbius ladders are also nontrivial biplanar graphs. They are not unit-distance, as can be proven by hand or using the "rhombus logic" of Globus and Parshall (2020) and Alexeev et al. (2025) (B. Alexeev, pers. comm., Aug. 9, 2025).

Every Möbius ladder is projective planar. Since the Klein bottle is the connected sum of two projective planes, every Möbius ladder has Klein bottle crossing number 0.

The numbers of directed Hamiltonian cycles for n=3, 4, ... are 12, 10, 16, 14, 20, 18, 24, ... (OEIS A124356), given by the closed form

|HC(n)|=2[(n+2)-(-1)^n].
(1)

The n-Möbius ladder graph has independence polynomial

I_n(x)=2^(-n)[-2^n(-x)^n+(x-sqrt(x(x+6)+1)+1)^n+(x+sqrt(x(x+6)+1)+1)^n].
(2)

Recurrence equations for the independence polynomial and matching polynomial are given by

I_n(x)=I_(n-1)(x)+x(x+2)I_(n-2)(x)+x^2I_(n-3)(x)
(3)
mu_n(x)=(x^2-1)mu_(n-1)(x)+2(1-x^2)mu_(n-2)(x)+(x^2+1)mu_(n-3)(x)-mu_(n-4)(x),
(4)

valid for n>=6 and n>=7, respectively.

When n is even, the bipartite double graph of the n-Möbius ladder is the prism graph Y_(2n). When n is odd, the Möbius ladder is bipartite, so its bipartite double graph is two disjoint copies of the original graph. The graph square of M_n is the circulant graph Ci_(2n)(1,2,n-1,n) and its graph cube is Ci_(2n)(1,2,3,n-2,n-1,n).

See also

Antiprism Graph, Circulant Graph, Crossed Prism Graph, Helm Graph, Ladder Graph, Prism Graph, Wagner Graph, Web Graph, Wheel Graph

Explore with Wolfram|Alpha

References

Alexeev, B.; Mixon, D. G.; and Parshall, H. "The Erdős Unit Distance Problem for Small Point Sets." 12 Feb 2025. https://arxiv.org/abs/2412.11914.Biggs, N. L. Algebraic Graph Theory, 2nd ed. Cambridge, England: Cambridge University Press, pp. 20-21, 1993.Gallian, J. "Labeling Prisms and Prism Related Graphs." Congr. Numer. 59, 89-100, 1987.Gallian, J. "Dynamic Survey of Graph Labeling." Elec. J. Combin., Dynamic Survey DS6, Oct. 30, 2025. https://doi.org/10.37236/27.Globus, A. and Parshall, H. "Small Unit-Distance Graphs in the Plane." Bull. Inst. Combin. Appl. 90, 107-138, 2020.Godsil, C. and Royle, G. Algebraic Graph Theory. New York: Springer-Verlag, pp. 118 and 131, 2001.Hladnik, M.; Marušič, D.; and Pisanski, T. "Cyclic Haar Graphs." Disc. Math. 244, 137-153, 2002.House of Graphs. Möbius Ladder Graphs. Wagner graph M8, Utility Graph K3,3, Mobius ladder M10, Mobius ladder M12, 7-Mobius ladder graph, and others.Jakobson, D. and Rivin, I. "On Some Extremal Problems in Graph Theory." 8 Jul 1999. https://arxiv.org/abs/math/9907050.McSorley, J. P. "Counting Structures in the Moebius Ladder." Disc. Math. 184, 137-164, 1998.Read, R. C. and Wilson, R. J. An Atlas of Graphs. Oxford, England: Oxford University Press, pp. 263 and 270, 1998.Sloane, N. J. A. Sequence A124356 in "The On-Line Encyclopedia of Integer Sequences."

Referenced on Wolfram|Alpha

Möbius Ladder

Cite this as:

Weisstein, Eric W. "Möbius Ladder." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/MoebiusLadder.html

Subject classifications