TOPICS
Search

Möbius Ladder

DOWNLOAD Mathematica NotebookDownload Wolfram Notebook
MoebiusLadders

A Möbius ladder, sometimes called a Möbius wheel (Jakobson and Rivin 1999), of order n is a simple graph obtained by introducing a twist in a prism graph of order n that is isomorphic to the circulant graph Ci_(2n)(1,n). 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 rung graph is isomorphic to the Haar graph H(2^(2n)+1).

Möbius ladders are Hamiltonian, graceful (Gallian 1987, Gallian 2018), 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) (pers. comm., B. Alexeev, Aug. 9, 2025).

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)

The bipartite double graph of the n-Möbius ladder is the prism graph Y_(2n). 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

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. DS6. Oct. 30, 2025. https://www.combinatorics.org/ojs/index.php/eljc/article/view/DS6.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.McSorley, J. P. "Counting Structures in the Moebius Ladder." Disc. Math. 184, 137-164, 1998.Jakobson, D. and Rivin, I. "On Some Extremal Problems in Graph Theory." 8 Jul 1999. http://arxiv.org/abs/math.CO/9907050.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