In graph theory, the Titze graph is an undirected cubic graph with 12 vertices and 18 edges. The graph is named after Heinrich Tietze , who showed in 1910 that the Mobius strip can be divided into six areas touching each other - three along the border of the ribbon and three along the center line - and therefore for graphs that can be embedded in the Mobius strip, six colors may be required [ 1] . The boundary segments of the Titz regions of the separation of the Mobius strip (including segments along the boundary of the ribbon itself) form an embedding of the Titz graph.
| Count Titze | |
|---|---|
 | |
| Named after | Heinrich Tietze |
| Top | 12 |
| Riber | eighteen |
| Radius | 3 |
| Diameter | 3 |
| Girth | 3 |
| Automorphisms | 12 ( D 6 ) |
| Chromatic number | 3 |
| Chromatic Index | four |
| The properties | Cubic Snark |
Content
- 1 Relationship with Count Petersen
- 2 Hamiltonian
- 3 Edge coloring and perfect matching
- 4 Additional properties
- 5 Gallery
- 6 See also
- 7 notes
- 8 Literature
Connection with Count Petersen
The Titz graph can be obtained from the Petersen graph by replacing one of its vertices with a triangle [2] . Like Count Titz, the Petersen graph serves as the boundaries of six mutually adjoining regions, but in the projective plane , and not on the Mobius strip. If we cut out the neighborhood of some vertex of this partition of the projective plane, the vertex is replaced by the boundaries of this hole, which gives exactly the construction of the Titz graph described above.
Hamiltonianity
Both the Titz graph and the Peterson graph are maximally non-Hamiltonian - they do not have a Hamiltonian cycle , but any two non-adjacent vertices can be connected by the Hamiltonian path [2] . The Titz graph and the Petersen graph are the only vertex 2-connected cubic non-Hamiltonian graphs with 12 or less vertices [3] .
Unlike the Petersen graph, the Tietze graph is not hypogamiltonian - removing one of the three vertices of the triangle forms a smaller graph that remains non-Hamiltonian.
Edge coloring and perfect matching
The edge coloring of the Titz graph requires four colors, that is, its chromatic index is 4. This is equivalent to the fact that the edges of the Titz graph can be divided into four matchings , but no less.
Count Titze satisfies part of the requirements for defining a snark - it is a cubic graph without bridges and its edges cannot be painted in 3 colors. However, some authors restrict snarks to graphs without 3-cycles and 4-cycles, and under these stronger conditions, the Titz graph is not a snark. Count Titze is isomorphic to graph J 3 , a graph from the infinite family of snarks “Flower” proposed by R. Isaacs in 1975 [4] .
Unlike Count Petersen, Count Titze can be covered with four perfect matchings . This property plays a key role in the proof that checking whether a graph can be covered by four matching is an NP-complete problem [5] .
Additional properties
The Titz graph has a chromatic number 3, a chromatic index 4, a girth of 3, and a diameter of 3. Its independence number is 5, the automorphism group is of the order of 12, and it is isomorphic to the dihedral group D 6 , a hexagon symmetry group including both rotations and reflections. This group contains two orbits of size 3 and one of size 6 at the vertices, and therefore this graph is not vertex transitive .
Gallery
The chromatic number of Count Titz is 3.
The chromatic index of the Titz graph is 4.
Count Titze has 2 intersections and is 1-planar .
Three-dimensional embedding of Count Titze.
See also
- Dürer graph and Franklin graph , two other 12-vertex cubic graphs.
Notes
- ↑ Tietze, 1910 , p. 155-159.
- ↑ 1 2 Clark, Entringer, 1983 , p. 57–68.
- ↑ Punnim, Saenpholphat, Thaithae, 2007 , p. 83–86.
- ↑ Isaacs, 1975 , p. 221–239.
- ↑ Esperet, Mazzuoccolo, 2014 , p. 144–157.
Literature
- L. Clark, R. Entringer. Smallest maximally nonhamiltonian graphs // Periodica Mathematica Hungarica. - 1983 .-- T. 14 , no. 1 . - DOI : 10.1007 / BF02023582 .
- Narong Punnim, Varaporn Saenpholphat, Sermsri Thaithae. Almost Hamiltonian cubic graphs // International Journal of Computer Science and Network Security. - 2007. - T. 7 , no. 1 .
- R. Isaacs. Infinite families of nontrivial trivalent graphs which are not Tait colorable // Amer. Math. Monthly - Mathematical Association of America, 1975.- T. 82 , no. 3 . - DOI : 10.2307 / 2319844 .
- Heinrich Tietze. Einige Bemerkungen zum Problem des Kartenfärbens auf einseitigen Flächen (Some remarks on the problem of map coloring on one-sided surfaces) // DMV Annual Report. - 1910. - T. 19 . (inaccessible link)
- L. Clark, R. Entringer. Smallest maximally nonhamiltonian graphs // Periodica Mathematica Hungarica. - 1983 .-- T. 14 , no. 1 . - DOI : 10.1007 / BF02023582 .
- L. Esperet, G. Mazzuoccolo. On cubic bridgeless graphs whose edge-set cannot be covered by four perfect matchings // Journal of Graph Theory. - 2014 .-- T. 77 , no. 2 . - DOI : 10.1002 / jgt.21778 . - arXiv : 1301.6926 .