Möbius ladder

Möbius ladder
Two views of the Möbius ladder M16.

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 (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

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 and Noy (2005) show that the Möbius ladders are uniquely determined by their chromatic 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 (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

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 1937 theorem of Klaus Wagner 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 (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 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 (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

See also

External links


Wikimedia Foundation. 2010.

Игры ⚽ Поможем написать реферат

Look at other dictionaries:

  • Möbius strip — This article is about the mathematical object. For musical group, see Mobius Band (band). A Möbius strip made with a piece of paper and tape. If an ant were to crawl along the length of this strip, it would return to its starting point having… …   Wikipedia

  • List of mathematics articles (M) — NOTOC M M estimator M group M matrix M separation M set M. C. Escher s legacy M. Riesz extension theorem M/M/1 model Maass wave form Mac Lane s planarity criterion Macaulay brackets Macbeath surface MacCormack method Macdonald polynomial Machin… …   Wikipedia

  • List of graphs — This partial list of graphs contains definitions of graphs and graph families which are known by particular names, but do not have a Wikipedia article of their own.For collected definitions of graph theory terms that do not refer to individual… …   Wikipedia

  • Graphe de Petersen — Schéma classique du graphe de Petersen, sous la forme d un pentagone et d un pentagramme concentriques, reliés par cinq rayons. Nombre de sommets 10 Nombre d arêtes 15 Distribution des degrés 3 régulier …   Wikipédia en Français

  • Graphe toroïdal — Un graphe plongé sur le tore de telle façon que les arêtes ne se coupent pas. En mathématiques, et plus précisément en théorie des graphes , un graphe G est toroïdal s il peut être plongé sur le tore, c et à dire que les sommets du graphe peuvent …   Wikipédia en Français

  • Petersen graph — Infobox graph name = Petersen graph image caption = The Petersen graph is most commonly drawn as a pentagon with a pentagram inside, with five spokes. namesake = Julius Petersen vertices = 10 edges = 15 radius = 2 diameter = 2 girth = 5 chromatic …   Wikipedia

  • Loop (graph theory) — In graph theory, a loop (also called a self loop) is an edge that connects a vertex to itself. A simple graph contains no loops.Depending on the context, a graph or a multigraph may be defined so as to either allow or disallow the presence of… …   Wikipedia

  • Toroidal graph — [ A graph (similar to the Heawood graph) embedded on the torus such that no edges cross. ] In mathematics, a graph G is toroidal if it can be embedded on the torus. In other words, the graph s vertices can be placed on a torus such that no edges… …   Wikipedia

  • Hadwiger conjecture (graph theory) — In graph theory, the Hadwiger conjecture (or Hadwiger s conjecture) states that, if an undirected graph G requires k or more colors in any vertex coloring, then one can find k disjoint connected subgraphs of G such that each subgraph is connected …   Wikipedia

  • Klaus Wagner (mathematician) — Klaus Wagner (March 31, 1910 – February 6, 2000) was a German mathematician. He studied topology at the University of Cologne under the supervision of Karl Dörge, who had been a student of Issai Schur. Wagner received his Ph.D. in 1937, and… …   Wikipedia

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”