Tietze's graph

Last updated
Tietze's subdivision of a Mobius strip into six mutually-adjacent regions. The vertices and edges of the subdivision form an embedding of Tietze's graph onto the strip. Tietze-Moebius.svg
Tietze's subdivision of a Möbius strip into six mutually-adjacent regions. The vertices and edges of the subdivision form an embedding of Tietze's graph onto the strip.
Tietze's graph
Tietze's graph.svg
The Tietze graph
Vertices 12
Edges 18
Radius 3
Diameter 3
Girth 3
Automorphisms 12 (D6)
Chromatic number 3
Chromatic index 4
Properties Cubic
Snark
Table of graphs and parameters

In the mathematical field of graph theory, Tietze's graph is an undirected cubic graph with 12 vertices and 18 edges. It is named after Heinrich Franz Friedrich Tietze, who showed in 1910 that the Möbius strip can be subdivided into six regions that all touch each other – three along the boundary of the strip and three along its center line – and therefore that graphs that are embedded onto the Möbius strip may require six colors. [1] The boundary segments of the regions of Tietze's subdivision (including the segments along the boundary of the Möbius strip itself) form an embedding of Tietze's graph.

Contents

Relation to Petersen graph

Tietze's graph may be formed from the Petersen graph by replacing one of its vertices with a triangle. [2] [3] Like the Tietze graph, the Petersen graph forms the boundary of six mutually touching regions, but on the projective plane rather than on the Möbius strip. If one cuts a hole from this subdivision of the projective plane, surrounding a single vertex, the surrounded vertex is replaced by a triangle of region boundaries around the hole, giving the previously described construction of the Tietze graph.

Hamiltonicity

Both Tietze's graph and the Petersen graph are maximally nonhamiltonian: they have no Hamiltonian cycle, but any two non-adjacent vertices can be connected by a Hamiltonian path. [2] Tietze's graph and the Petersen graph are the only 2-vertex-connected cubic non-Hamiltonian graphs with 12 or fewer vertices. [4]

Unlike the Petersen graph, Tietze's graph is not hypohamiltonian: removing one of its three triangle vertices forms a smaller graph that remains non-Hamiltonian.

Edge coloring and perfect matchings

Edge coloring Tietze's graph requires four colors; that is, its chromatic index is 4. Equivalently, the edges of Tietze's graph can be partitioned into four matchings, but no fewer.

Tietze's graph matches part of the definition of a snark: it is a cubic bridgeless graph that is not 3-edge-colorable. However, most authors restrict snarks to graphs without 3-cycles, so Tietze's graph is not generally considered to be a snark. Nevertheless, it is isomorphic to the graph J3, part of an infinite family of flower snarks introduced by R. Isaacs in 1975. [5]

Unlike the Petersen graph, the Tietze graph can be covered by four perfect matchings. This property plays a key role in a proof that testing whether a graph can be covered by four perfect matchings is NP-complete. [6]

Additional properties

Tietze's graph has chromatic number 3, chromatic index 4, girth 3 and diameter 3. The independence number is 5. Its automorphism group has order 12, and is isomorphic to the dihedral group D6, the group of symmetries of a hexagon, including both rotations and reflections. This group has two orbits of size 3 and one of size 6 on vertices, and thus this graph is not vertex-transitive.

See also

Notes

  1. Tietze, Heinrich (1910), "Einige Bemerkungen zum Problem des Kartenfärbens auf einseitigen Flächen" [Some remarks on the problem of map coloring on one-sided surfaces](PDF), DMV Annual Report, 19: 155–159
  2. 1 2 Clark, L.; Entringer, R. (1983), "Smallest maximally nonhamiltonian graphs", Periodica Mathematica Hungarica, 14 (1): 57–68, doi:10.1007/BF02023582
  3. Weisstein, Eric W. "Tietze's Graph". MathWorld .
  4. Punnim, Narong; Saenpholphat, Varaporn; Thaithae, Sermsri (2007), "Almost Hamiltonian cubic graphs" (PDF), International Journal of Computer Science and Network Security, 7 (1): 83–86
  5. Isaacs, R. (1975), "Infinite families of nontrivial trivalent graphs which are not Tait colorable", Amer. Math. Monthly, Mathematical Association of America, 82 (3): 221–239, doi:10.2307/2319844, JSTOR   2319844 .
  6. Esperet, L.; Mazzuoccolo, G. (2014), "On cubic bridgeless graphs whose edge-set cannot be covered by four perfect matchings", Journal of Graph Theory, 77 (2): 144–157, arXiv: 1301.6926 , doi:10.1002/jgt.21778, MR   3246172 .

Related Research Articles

Petersen graph Cubic graph with 10 vertices and 15 edges

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 named after Julius Petersen, who in 1898 constructed it to be the smallest bridgeless cubic graph with no three-edge-coloring.

This is a glossary of graph theory. Graph theory is the study of graphs, systems of nodes or vertices connected in pairs by lines or edges.

Outerplanar graph

In graph theory, an outerplanar graph is a graph that has a planar drawing for which all vertices belong to the outer face of the drawing.

Edge coloring Problem of coloring a graphs edges such that meeting edges do not match

In graph theory, an edge coloring of a graph is an assignment of "colors" to the edges of the graph so that no two incident edges have the same color. For example, the figure to the right shows an edge coloring of a graph by the colors red, blue, and green. Edge colorings are one of several different types of graph coloring. The edge-coloring problem asks whether it is possible to color the edges of a given graph using at most k different colors, for a given value of k, or with the fewest possible colors. The minimum required number of colors for the edges of a given graph is called the chromatic index of the graph. For example, the edges of the graph in the illustration can be colored by three colors but cannot be colored by two colors, so the graph shown has chromatic index three.

Snark (graph theory) 3-regular graph with no 3-edge-coloring

In the mathematical field of graph theory, a snark is an undirected graph with exactly three edges per vertex whose edges cannot be colored with only three colors. In order to avoid trivial cases, snarks are often restricted to have additional requirements on their connectivity and on the length of their cycles. Infinitely many snarks are known to exist.

Cubic graph Graph with all vertices of degree 3

In the mathematical field of graph theory, a cubic graph is a graph in which all vertices have degree three. In other words, a cubic graph is a 3-regular graph. Cubic graphs are also called trivalent graphs.

Heawood graph Undirected graph with 14 vertices

In the mathematical field of graph theory, the Heawood graph is an undirected graph with 14 vertices and 21 edges, named after Percy John Heawood.

Desargues graph

In the mathematical field of graph theory, the Desargues graph is a distance-transitive cubic graph with 20 vertices and 30 edges. It is named after Girard Desargues, arises from several different combinatorial constructions, has a high level of symmetry, is the only known non-planar cubic partial cube, and has been applied in chemical databases.

Some of the finite structures considered in graph theory have names, sometimes inspired by the graph's topology, and sometimes after their discoverer. A famous example is the Petersen graph, a concrete graph on 10 vertices that appears as a minimal example or counterexample in many different contexts.

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.

Hypohamiltonian graph

In the mathematical field of graph theory, a graph G is said to be hypohamiltonian if G itself does not have a Hamiltonian cycle but every graph formed by removing a single vertex from G is Hamiltonian.

Cycle double cover Cycles in a graph that cover each edge twice

In graph-theoretic mathematics, a cycle double cover is a collection of cycles in an undirected graph that together include each edge of the graph exactly twice. For instance, for any polyhedral graph, the faces of a convex polyhedron that represents the graph provide a double cover of the graph: each edge belongs to exactly two faces.

Dürer graph Graph with a triangular truncated trapezohedron as its skeleton

In the mathematical field of graph theory, the Dürer graph is an undirected graph with 12 vertices and 18 edges. It is named after Albrecht Dürer, whose 1514 engraving Melencolia I includes a depiction of Dürer's solid, a convex polyhedron having the Dürer graph as its skeleton. Dürer's solid is one of only four well-covered simple convex polyhedra.

Generalized Petersen graph Family of cubic graphs formed from regular and star polygons

In graph theory, the generalized Petersen graphs are a family of cubic graphs formed by connecting the vertices of a regular polygon to the corresponding vertices of a star polygon. They include the Petersen graph and generalize one of the ways of constructing the Petersen graph. The generalized Petersen graph family was introduced in 1950 by H. S. M. Coxeter and was given its name in 1969 by Mark Watkins.

Flower snark Infinite family of graphs

In the mathematical field of graph theory, the flower snarks form an infinite family of snarks introduced by Rufus Isaacs in 1975.

Clebsch graph One of two different regular graphs with 16 vertices

In the mathematical field of graph theory, the Clebsch graph is either of two complementary graphs on 16 vertices, a 5-regular graph with 40 edges and a 10-regular graph with 80 edges. The 80-edge graph is the dimension-5 halved cube graph; it was called the Clebsch graph name by Seidel (1968) because of its relation to the configuration of 16 lines on the quartic surface discovered in 1868 by the German mathematician Alfred Clebsch. The 40-edge variant is the dimension-5 folded cube graph; it is also known as the Greenwood–Gleason graph after the work of Robert E. Greenwood and Andrew M. Gleason (1955), who used it to evaluate the Ramsey number R(3,3,3) = 17.

Nauru graph

In the mathematical field of graph theory, the Nauru graph is a symmetric bipartite cubic graph with 24 vertices and 36 edges. It was named by David Eppstein after the twelve-pointed star in the flag of Nauru.

Double-star snark

In the mathematical field of graph theory, the double-star snark is a snark with 30 vertices and 45 edges.

Petersens theorem

In the mathematical discipline of graph theory, Petersen's theorem, named after Julius Petersen, is one of the earliest results in graph theory and can be stated as follows:

Petersen's Theorem. Every cubic, bridgeless graph contains a perfect matching.

The Petersen Graph is a mathematics book about the Petersen graph and its applications in graph theory. It was written by Derek Holton and John Sheehan, and published in 1993 by the Cambridge University Press as volume 7 in their Australian Mathematical Society Lecture Series.