Möbius ladder (denoted Mₙ) is a concept in graph theory: a cubic, circulant graph formed from an n-cycle (where n is an even number) by adding edges called "rungs" that connect opposite pairs of vertices in the cycle. It is named for its topological resemblance to a Möbius strip, as (with the exception of M₆) the graph contains exactly n/2 four-cycles that link together by shared edges to form a topological Möbius strip. The term was introduced and first studied by Richard K. Guy and Frank Harary in 1967.
Definition and Notation
For an even integer n, the Möbius ladder Mₙ has n vertices and n + n/2 edges. It is a cubic graph (every vertex has degree 3) and a circulant graph, denoted Ci₂ₙ(1, n). The vertices are arranged in a cycle, and each vertex is connected to its two cycle neighbors as well as to the vertex opposite it on the cycle.
Properties
- Girth: 4 (for even n > 4)
- Chromatic number: 3
- Chromatic index: 3
- Genus: 1 (for even n > 4); the graph is toroidal and can be embedded without crossings on a torus or projective plane.
- Planarity: For every even n > 4, Mₙ is a nonplanar apex graph with crossing number 1.
- Vertex-transitivity: Möbius ladders are vertex-transitive but (except for M₄ and M₆) are not edge-transitive.
- Bipartiteness: When n ≡ 2 (mod 4), Mₙ is bipartite; when n ≡ 0 (mod 4), it is not bipartite.
- Spanning trees: M₈ has 392 spanning trees; M₆ and M₈ have the most spanning trees among all cubic graphs with the same number of vertices.
Special Cases
- M₄ (the 4-vertex Möbius ladder) is isomorphic to the complete graph K₄.
- M₆ is isomorphic to the utility graph K₃,₃.
- M₈ is known as the Wagner graph, which plays a key role in the theory of graph minors. Klaus Wagner (1937) proved that graphs with no K₅ minor can be formed by combining planar graphs and M₈ via clique-sum operations.
Graph Minors
Möbius ladders are important in graph minor theory. The Wagner graph (M₈) is a forbidden minor in characterizations of planar graphs. Gubser (1996) showed that 3-connected almost-planar graphs are Möbius ladders or members of a small number of other families. Maharry (2000) demonstrated that almost all graphs without a cube minor can be derived from Möbius ladders.
Applications
- Chemistry: Walba, Richards, and Haltiwanger (1982) first synthesized molecular structures in the form of a Möbius ladder. The structure has relevance to DNA molecules due to their ladder-like form. Erica Flapan (1989) studied the mathematical symmetries of embeddings of Möbius ladders in ℝ³, showing that those with an odd number of rungs are topologically chiral.
- Physics: Möbius ladders have been used as the shape of superconducting rings in experiments studying the effects of conductor topology on electron interactions.
- Combinatorial optimization: In computer science, Möbius ladder constraints define facets of polytopes used in integer programming approaches to set packing and linear ordering problems.
