In the mathematical field of graph theory, Tietze's graph is an undirectedcubic 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.
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 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.
Hamiltonicityedit
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 matchingsedit
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 propertiesedit
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.
^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
^Punnim, Narong; Saenpholphat, Varaporn; Thaithae, Sermsri (2007), "Almost Hamiltonian cubic graphs" (PDF), International Journal of Computer Science and Network Security, 7 (1): 83–86
^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.
^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.
December 02, 2023
tietze, graph, mathematical, field, graph, theory, undirected, cubic, graph, with, vertices, edges, named, after, heinrich, franz, friedrich, tietze, showed, 1910, that, möbius, strip, subdivided, into, regions, that, touch, each, other, three, along, boundary. 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 Mobius 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 Mobius strip may require six colors 1 The boundary segments of the regions of Tietze s subdivision including the segments along the boundary of the Mobius strip itself form an embedding of Tietze s graph 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 s graphThe Tietze graphVertices12Edges18Radius3Diameter3Girth3Automorphisms12 D6 Chromatic number3Chromatic index4PropertiesCubicSnarkTable of graphs and parameters Contents 1 Relation to Petersen graph 2 Hamiltonicity 3 Edge coloring and perfect matchings 4 Additional properties 5 Gallery 6 See also 7 NotesRelation to Petersen graph editTietze 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 Mobius 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 editBoth 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 editEdge 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 editTietze 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 Gallery edit nbsp The chromatic number of the Tietze graph is 3 nbsp The chromatic index of the Tietze graph is 4 nbsp The Tietze graph has crossing number 2 and is 1 planar nbsp A three dimensional embedding of the Tietze graph nbsp Wikimedia Commons has media related to Tietze s graph See also editDurer graph and Franklin graph two other 12 vertex cubic graphsNotes edit Tietze Heinrich 1910 Einige Bemerkungen zum Problem des Kartenfarbens auf einseitigen Flachen Some remarks on the problem of map coloring on one sided surfaces PDF DMV Annual Report 19 155 159 a b Clark L Entringer R 1983 Smallest maximally nonhamiltonian graphs Periodica Mathematica Hungarica 14 1 57 68 doi 10 1007 BF02023582 Weisstein Eric W Tietze s Graph MathWorld Punnim Narong Saenpholphat Varaporn Thaithae Sermsri 2007 Almost Hamiltonian cubic graphs PDF International Journal of Computer Science and Network Security 7 1 83 86 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 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 Retrieved from https en wikipedia org w index php title Tietze 27s graph amp oldid 1172689555, wikipedia, wiki, book, books, library,
