Möbius ladder

From Wikipedia, the free encyclopedia
Two views of the Möbius ladder M16. For an animation showing the transformation between the two views, see this file.
View of the Möbius ladder M16 showing strip-like layout.

In graph theory, the Möbius ladder Mn 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 M6 = K3,3) Mn has exactly n/2 4-cycles[1] 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).

Properties

Every Möbius ladder is a nonplanar apex graph. Möbius ladders have crossing number one, and can be embedded without crossings on a torus or projective plane. Thus, they are examples of toroidal graphs. Li (2005) explores embeddings of these graphs onto higher genus surfaces.

Möbius ladders are vertex-transitive but (again with the exception of M6) 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), Mn is bipartite. When n ≡ 0 (mod 4), by Brooks' theorem Mn has chromatic number 3. De Mier & Noy (2004) show that the Möbius ladders are uniquely determined by their Tutte polynomials.

The Möbius ladder M8 has 392 spanning trees; it and M6 have the most spanning trees among all cubic graphs with the same number of vertices.[2] However, the 10-vertex cubic graph with the most spanning trees is the Petersen graph, which is not a Möbius ladder.

The Tutte polynomials of the Möbius ladders may be computed by a simple recurrence relation.[3]

Graph minors

The Wagner graph M8

Möbius ladders play an important role in the theory of graph minors. The earliest result of this type is a theorem of Klaus Wagner (1937) that graphs with no K5 minor can be formed by using clique-sum operations to combine planar graphs and the Möbius ladder M8; for this reason M8 is 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 (2000) 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, Richards & Haltiwanger (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,[4] 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 R3.

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.[5]

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.[6]

See also

Notes

  1. McSorley (1998).
  2. Jakobson & Rivin (1999); Valdes (1991).
  3. Biggs, Damerell & Sands (1972).
  4. Simon (1992).
  5. Mila, Stafford & Capponi (1998); Deng, Xu & Liu (2002).
  6. Bolotashvili, Kovalev & Girlich (1999); Borndörfer & Weismantel (2000); Grötschel, Jünger, and Reinelt (1985a, 1985b); Newman & Vempala (2001)

References

External links

This article is issued from Wikipedia. The text is available under the Creative Commons Attribution/Share Alike; additional terms may apply for the media files.