MöBIUS LADDER

In the mathematical area of graph theory, the 'Möbius ladder' ''M''_''n'' is a cubic circulant graph with an even number ''n'' of vertices, formed from an ''n''-cycle by adding edges (called "rungs") connecting opposite pairs of vertices in the cycle. It is so-named because (with the exception of ''M''₆ = ''K''_3,3) ''M''_''n'' has exactly ''n''/2 4-cycles (McSorley 1998) which link together by their shared edges to form a topological Möbius strip. Möbius ladders were named and first studied by Guy and Harary (1967).

Contents

Properties

Graph minors

Chemistry and Physics

Combinatorial optimization

References

See also

External links

Properties

Every Möbius ladder is nonplanar. Möbius ladders have crossing number one, and can be embedded without crossings on a torus or projective plane. Li (2005) explores embeddings of these graphs onto higher genus surfaces.
Möbius ladders are vertex-transitive but (again with the exception of ''M''₆) not edge-transitive: each edge from the cycle from which the ladder is formed belongs to a single 4-cycle, while each rung belongs to two such cycles.
When ''n'' ≡ 2 (mod 4), ''M''_''n'' is bipartite. When ''n'' ≡ 0 (mod 4), by Brooks' theorem ''M''_''n'' has chromatic number 3. De Mier and Noy (2005) show that the Möbius ladders are uniquely determined by their chromatic polynomials.
The Möbius ladder ''M''₈ has 392 spanning trees; it and ''M''₆ have the most spanning trees among all cubic graphs with the same number of vertices (Jakobson and Rivin 1999; Valdes 1991). However, the 10-vertex graph with the most spanning trees is the Petersen graph, which is not a Möbius ladder.

Graph minors

Möbius ladders play an important role in the theory of graph minors. The earliest result of this type is a theorem of Wagner (1937) that graphs with no ''K''₅ minor can be formed by simple operations that combine planar graphs and the Möbius ladder ''M''₈; for this reason ''M''₈ is sometimes called the 'Wagner graph'.
Gubser (1996) defines an ''almost-planar graph'' to be a nonplanar graph for which every nontrivial minor is planar; he shows that 3-connected almost-planar graphs are Möbius ladders or members of a small number of other families, and that other almost-planar graphs can be formed from these by a sequence of simple operations.
Maharry (2001) shows that almost all graphs that do not have a cube minor can be derived by a sequence of simple operations from Möbius ladders.

Chemistry and Physics

Walba et al (1982) first synthesized molecular structures in the form of a Möbius ladder, and since then this structure has been of interest in chemistry and chemical stereography (Simon 1993), especially in view of the ladder-like form of DNA molecules. With this application in mind, Flapan (1989) studies the mathematical symmetries of embeddings of Möbius ladders in 'R'³.
Möbius ladders have also been used as the shape of a superconducting ring in experiments to study the effects of conductor topology on electron interactions (Mila et al 1998; Deng et al 2002).

Combinatorial optimization

Möbius ladders have also been used in computer science, as part of integer programming approaches to problems of set packing and linear ordering. Certain configurations within these problems can be used to define facets of the polytope describing a linear programming relaxation of the problem; these facets are called Möbius ladder constraints (Bolotashvili et al 1999; Borndörfer and Weismantel 2000; Grötschel et al 1985a, 1985b; Newman and Vempala 2004).

References

★ New facets of the linear ordering polytope, Bolotashvili, G.; Kovalev, M.; Girlich, E., , , SIAM J. Discrete Math., 1999

★ Set packing relaxations of some integer programs, Borndörfer, Ralf; Weismantel, Robert, , , Mathematical Programming, Series A, 2000

★ {{cite journal
| author = Deng Wen-Ji; Xu Ji-Huan; Liu Ping
| title = Period halving of persistent currents in mesoscopic Möbius ladders
| journal = Chinese Physics Letters
| year = 2002
| volume = 19
| pages = 988–991
| doi = 10.1088/0256-307X/19/7/333
| id =

★ Symmetries of Möbius ladders, Flapan, Erica, , , Mathematische Annalen, 1989

★ On the maximum acyclic subgraph polytope, Grötschel, M.; Jünger, M.; Reinelt, G., , , Mathematical Programming, 1985

★ Facets of the linear ordering polytope, Grötschel, M.; Jünger, M.; Reinelt, G., , , Mathematical Programming, 1985

★ A characterization of almost-planar graphs, Gubser, Bradley S., , , Combin. Probab. Comput., 1996

★ On the Möbius ladders, Guy, Richard K.; Harary, Frank, , , Canad. Math. Bull., 1967

★ {{cite journal
| author = Jakobson, Dmitry; Rivin, Igor
| title = On some extremal problems in graph theory
| year = 1999
| id =

★ Genus distributions of Möbius ladders, Li, De-ming, , , Northeastern Mathematics Journal, 2005

★ A characterization of graphs with no cube minor, Maharry, John, , , Journal of Combinatorial Theory, Series B, 2000

★ Counting structures in the Möbius ladder, McSorley, John P., , , Discrete Mathematics, 1998

★ On graphs determined by their Tutte polynomials, de Mier, Anna; Noy, Marc, , , Graphs Combin., 2004

★ Persistent currents in a Möbius ladder: A test of interchain coherence of interacting electrons, Mila, Frédéric; Stafford, C. A.; Capponi, Sylvain, , , Physical Review B, 1998

★

★

★ Extremal properties of spanning trees in cubic graphs, Valdes, L., , , Congr. Numer., 1991

★ Über eine Eigenschaft der ebenen Komplexe, Wagner, K., , , Mathematische Annalen, 1937

★ Total synthesis of the first molecular Möbius strip, Walba, D.; Richards, R.; Haltiwanger, R.C., , , Journal of the American Chemical Society, 1982

See also

★ Möbius strip

★ Strange loop

★ Klein bottle

External links

★