HOME

TheInfoList



OR:

In
graph theory In mathematics and computer science, graph theory is the study of ''graph (discrete mathematics), graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of ''Vertex (graph ...
, the Möbius ladder , for even numbers , is formed from an by adding edges (called "rungs") connecting opposite pairs of vertices in the cycle. It is a
cubic Cubic may refer to: Science and mathematics * Cube (algebra), "cubic" measurement * Cube, a three-dimensional solid object bounded by six square faces, facets or sides, with three meeting at each vertex ** Cubic crystal system, a crystal system w ...
, circulant graph, so-named because (with the exception of (the utility graph ), has exactly four-cycles which link together by their shared edges to form a topological
Möbius strip In mathematics, a Möbius strip, Möbius band, or Möbius loop is a Surface (topology), surface that can be formed by attaching the ends of a strip of paper together with a half-twist. As a mathematical object, it was discovered by Johann Bened ...
. Möbius ladders were named and first studied by .


Properties

For every even , the Möbius ladder is a nonplanar apex graph, meaning that it cannot be drawn without crossings in the plane but removing one vertex allows the remaining graph to be drawn without crossings. These graphs have crossing number one, and can be embedded without crossings on a
torus In geometry, a torus (: tori or toruses) is a surface of revolution generated by revolving a circle in three-dimensional space one full revolution about an axis that is coplanarity, coplanar with the circle. The main types of toruses inclu ...
or
projective plane In mathematics, a projective plane is a geometric structure that extends the concept of a plane (geometry), plane. In the ordinary Euclidean plane, two lines typically intersect at a single point, but there are some pairs of lines (namely, paral ...
. Thus, they are examples of toroidal graphs. explores embeddings of these graphs onto higher genus surfaces. Möbius ladders are vertex-transitive – they have symmetries taking any vertex to any other vertex – but (with the exceptions of and ) they are not edge-transitive. The edges from the cycle from which the ladder is formed can be distinguished from the rungs of the ladder, because each cycle edge belongs to a single 4-cycle, while each rung belongs to two such cycles. Therefore, there is no symmetry taking a cycle edge to a rung edge or vice versa. When ''n'' ≡ 2 (mod 4), ''M''''n'' is bipartite. When ''n'' ≡ 0 (mod 4), it is not bipartite. The endpoints of each rung are an even distance apart in the initial cycle, so adding each rung creates an odd cycle. In this case, because the graph is 3-regular but not bipartite, by
Brooks' theorem In graph theory, Brooks' theorem states a relationship between the maximum degree (graph theory), degree of a graph and its chromatic number. According to the theorem, in a connected graph in which every vertex has at most Δ neighbors, the vertic ...
it has chromatic number 3. show that the Möbius ladders are uniquely determined by their Tutte polynomials. The Möbius ladder ''M''8 has 392
spanning tree In the mathematical field of graph theory, a spanning tree ''T'' of an undirected graph ''G'' is a subgraph that is a tree which includes all of the vertices of ''G''. In general, a graph may have several spanning trees, but a graph that is no ...
s; it and ''M''6 have the most spanning trees among all cubic graphs with the same number of vertices. However, the 10-vertex cubic graph with the most spanning trees is the
Petersen graph In the mathematical field of graph theory, the Petersen graph is an undirected graph with 10 vertices and 15 edges. It is a small graph that serves as a useful example and counterexample for many problems in graph theory. The Petersen graph i ...
, which is not a Möbius ladder. The Tutte polynomials of the Möbius ladders may be computed by a simple
recurrence relation In mathematics, a recurrence relation is an equation according to which the nth term of a sequence of numbers is equal to some combination of the previous terms. Often, only k previous terms of the sequence appear in the equation, for a parameter ...
.


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 that graphs with no ''K''5 minor can be formed by using clique-sum operations to combine planar graphs and the Möbius ladder ''M''8; for this reason ''M''8 is called the Wagner graph. 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. shows that almost all graphs that do not have a
cube A cube or regular hexahedron is a three-dimensional space, three-dimensional solid object in geometry, which is bounded by six congruent square (geometry), square faces, a type of polyhedron. It has twelve congruent edges and eight vertices. It i ...
minor can be derived by a sequence of simple operations from Möbius ladders.


Chemistry and physics

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, especially in view of the ladder-like form of DNA molecules. With this application in mind, studies the mathematical symmetries of embeddings of Möbius ladders in R3. In particular, as she shows, every three-dimensional embedding of a Möbius ladder with an odd number of rungs is topologically
chiral Chirality () is a property of asymmetry important in several branches of science. The word ''chirality'' is derived from the Greek language, Greek (''kheir''), "hand", a familiar chiral object. An object or a system is ''chiral'' if it is dist ...
: it cannot be converted into its mirror image by a continuous deformation of space without passing one edge through another. On the other hand, Möbius ladders with an
even number In mathematics, parity is the property of an integer of whether it is even or odd. An integer is even if it is divisible by 2, and odd if it is not.. For example, −4, 0, and 82 are even numbers, while −3, 5, 23, and 69 are odd numbers. The ...
of rungs all do have embeddings into R3 that can be deformed into their mirror images. 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.


Combinatorial optimization

Möbius ladders have also been used in
computer science Computer science is the study of computation, information, and automation. Computer science spans Theoretical computer science, theoretical disciplines (such as algorithms, theory of computation, and information theory) to Applied 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 In elementary geometry, a polytope is a geometric object with flat sides ('' faces''). Polytopes are the generalization of three-dimensional polyhedra to any number of dimensions. Polytopes may exist in any general number of dimensions as an ...
describing a
linear programming Linear programming (LP), also called linear optimization, is a method to achieve the best outcome (such as maximum profit or lowest cost) in a mathematical model whose requirements and objective are represented by linear function#As a polynomia ...
relaxation of the problem; these facets are called Möbius ladder constraints.; ; ;


See also

* Ladder graph *
Prism graph In the mathematics, mathematical field of graph theory, a prism graph is a Graph (discrete mathematics), graph that has one of the prism (geometry), prisms as its skeleton. Examples The individual graphs may be named after the associated solid: * ...


Notes


References

* * * * * * * * * * * * * * * * * * * *


External links

* {{DEFAULTSORT:Mobius ladder Parametric families of graphs Regular graphs