Tietze's graph
| Tietze's graph | |
|---|---|
 The Tietze graph | |
| Vertices | 12 |
| Edges | 18 |
| Diameter | 3 |
| Girth | 3 |
| Automorphisms | 12 (D6) |
| Chromatic number | 3 |
| Chromatic index | 4 |
| Properties |
Cubic Snark |
In the mathematical field of graph theory, Tietze's graph is an undirected cubic graph with 12 vertices and 18 edges, formed by applying a Y-Δ transform to the Petersen graph and thereby replacing one of its vertices by a triangle.[1][2] 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 an 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.
Like the Petersen graph it is maximally nonhamiltonian: it has no Hamiltonian cycle, but any two non-adjacent vertices can be connected by a Hamiltonian path.[1] It and the Petersen graph are the only 2-vertex-connected cubic non-Hamiltonian graphs with 12 or fewer vertices.[3]
Tietze's graph matches part of the definition of a snark: it is a cubic bridgeless graph that is not 3-edge-colorable. However, some authors restrict snarks to graphs without 3-cycles and 4-cycles, and under this more restrictive definition Tietze's graph is not a snark. Tietze's graph is isomorphic to the graph J3, part of an infinite family of flower snarks introduced by R. Isaacs in 1975.[4]
Gallery
-
The chromatic number of the Tietze graph is 3.
-
The chromatic index of the Tietze graph is 4.
-
The Tietze graph can be drawn on a Möbius strip with no crossings.[1]
Cite error: There are <ref> tags on this page, but the references will not show without a {{reflist}} template (see the help page).
 |
Wikimedia Commons has media related to Tietze's graph. |
Notes
- ↑ 1.0 1.1 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", 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.