Möbius ladder
   HOME

TheInfoList



OR:

In
graph theory In mathematics, graph theory is the study of ''graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conne ...
, 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, circulant graph, so-named because (with the exception of (the
utility graph As a topic of economics, utility is used to model worth or value. Its usage has evolved significantly over time. The term was introduced initially as a measure of pleasure or happiness as part of the theory of utilitarianism by moral philosopher ...
), 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 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 Benedict Listing and Augu ...
. Möbius ladders were named and first studied by .


Properties

For every even , the Möbius ladder is a nonplanar
apex graph In graph theory, a branch of mathematics, an apex graph is a graph that can be made planar by the removal of a single vertex. The deleted vertex is called an apex of the graph. It is ''an'' apex, not ''the'' apex because an apex graph may have mo ...
, 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 (plural tori, colloquially donut or doughnut) is a surface of revolution generated by revolving a circle in three-dimensional space about an axis that is coplanar with the circle. If the axis of revolution does not tou ...
or
projective plane In mathematics, a projective plane is a geometric structure that extends the concept of a plane. In the ordinary Euclidean plane, two lines typically intersect in a single point, but there are some pairs of lines (namely, parallel lines) that do ...
. Thus, they are examples of
toroidal graph In the mathematical field of graph theory, a toroidal graph is a graph that can be embedded on a torus. In other words, the graph's vertices can be placed on a torus such that no edges cross. Examples Any graph that can be embedded in a plane ...
s. explores embeddings of these graphs onto higher genus surfaces. Möbius ladders are
vertex-transitive In geometry, a polytope (e.g. a polygon or polyhedron) or a tiling is isogonal or vertex-transitive if all its vertices are equivalent under the symmetries of the figure. This implies that each vertex is surrounded by the same kinds of face in ...
– they have symmetries taking any vertex to any other vertex – but (with the exceptions of and ) they are not
edge-transitive In geometry, a polytope (for example, a polygon or a polyhedron) or a tiling is isotoxal () or edge-transitive if its symmetries act transitively on its edges. Informally, this means that there is only one type of edge to the object: given two ...
. 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 of a graph and its chromatic number. According to the theorem, in a connected graph in which every vertex has at most Δ neighbors, the vertices can be colored with o ...
it has
chromatic number In graph theory, graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called "colors" to elements of a graph subject to certain constraints. In its simplest form, it is a way of coloring the vertices o ...
3. show that the Möbius ladders are uniquely determined by their
Tutte polynomial The Tutte polynomial, also called the dichromate or the Tutte–Whitney polynomial, is a graph polynomial. It is a polynomial in two variables which plays an important role in graph theory. It is defined for every undirected graph G and contai ...
s. 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 not ...
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 is n ...
, which is not a Möbius ladder. The
Tutte polynomial The Tutte polynomial, also called the dichromate or the Tutte–Whitney polynomial, is a graph polynomial. It is a polynomial in two variables which plays an important role in graph theory. It is defined for every undirected graph G and contai ...
s 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 In graph theory, a branch of mathematics, a clique-sum is a way of combining two graphs by gluing them together at a clique, analogous to the connected sum operation in topology. If two graphs ''G'' and ''H'' each contain cliques of equal size, th ...
operations to combine planar graphs and the Möbius ladder ''M''8; for this reason ''M''8 is called the
Wagner graph In the mathematical field of graph theory, the Wagner graph is a 3-regular graph with 8 vertices and 12 edges. It is the 8-vertex Möbius ladder graph. Properties As a Möbius ladder, the Wagner graph is nonplanar but has crossing number one, ...
. 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 In geometry, a cube is a three-dimensional solid object bounded by six square faces, facets or sides, with three meeting at each vertex. Viewed from a corner it is a hexagon and its net is usually depicted as a cross. The cube is the only r ...
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 (''kheir''), "hand", a familiar chiral object. An object or a system is ''chiral'' if it is distinguishable from ...
: 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 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 Superconductivity is a set of physical properties observed in certain materials where Electrical resistance and conductance, electrical resistance vanishes and magnetic field, magnetic flux fields are expelled from the material. Any material e ...
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, automation, and information. Computer science spans theoretical disciplines (such as algorithms, theory of computation, information theory, and automation) to Applied science, practical discipli ...
, as part of
integer programming An integer programming problem is a mathematical optimization or Constraint satisfaction problem, feasibility program in which some or all of the variables are restricted to be integers. In many settings the term refers to integer linear programmin ...
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 -d ...
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 are represented by linear function#As a polynomial function, li ...
relaxation of the problem; these facets are called Möbius ladder constraints.; ; ;


See also

* Ladder graph *
Prism graph In the mathematical field of graph theory, a prism graph is a graph that has one of the prisms as its skeleton. Examples The individual graphs may be named after the associated solid: * Triangular prism graph – 6 vertices, 9 edges * Cubical gra ...


Notes


References

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


External links

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