Möbius Ladder

 

A Möbius ladder, sometimes called a Möbius wheel (Jakobson and Rivin 1999), of order  is a simple graph obtained by introducing a twist in a prism graph of order  that is isomorphic to the circulant graph . Möbius ladders are sometimes denoted .

The 4-Möbius ladder is known as the Wagner graph. The -Möbius ladder rung graph is isomorphic to the Haar graph .

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 , 4, ... are 12, 10, 16, 14, 20, 18, 24, ... (OEIS A124356), given by the closed form

(1)

The -Möbius ladder graph has independence polynomial

(2)

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

			(3)
			(4)

The bipartite double graph of the -Möbius ladder is the prism graph .

---

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."

مواضيع ذات صلة

Minimum Spanning Tree

Maximum Leaf Number

Lobster Graph

Labeled Tree

Internal Path Length

Red-Black Tree

Pseudotree

Pseudoforest

Prüfer Code

Planted Tree

Planted Planar Tree

Graph Strength