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.

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

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. Dec. 21, 2018. https://www.combinatorics.org/ojs/index.php/eljc/article/view/DS6.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."

Cite this as:

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

Subject classifications