Tietze's graph

Tietze's graph
Tietze's graph
Tietze's graph.svg
The Tietze's graph
Vertices 12
Edges 18
Diameter 3
Girth 3
Automorphisms 12 (D6)
Chromatic number 3
Chromatic index 4
Properties Cubic
Snark
v · mathematical field of graph theory, the 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. 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.

Like the Petersen graph it is maximally nonhamiltonian: it has no Hamiltonian cycle, but any two 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's graph is 3.

  • The chromatic index of the Tietze's graph is 4.

  • The Tietze graph can be drawn on a Möbius strip with no crossings.[5]

Notes

  1. ^ a b Clark, L.; Entringer, R. (1983), "Smallest maximally nonhamiltonian graphs", Periodica Mathematica Hungarica 14 (1): 57–68, doi:10.1007/BF02023582 
  2. ^ Weisstein, Eric W., "Tietze's Graph" from MathWorld.
  3. ^ Punnim, Narong; Saenpholphat, Varaporn; Thaithae, Sermsri (2007), "Almost Hamiltonian cubic graphs", International Journal of Computer Science and Network Security 7 (1): 83–86, http://paper.ijcsns.org/07_book/200701/200701A12.pdf 
  4. ^ 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 .
  5. ^ Bondy, J. A.; Murty, U. S. R. (1976), "Appendix III", Graph Theory with Applications, New York: North Holland, p. 243, http://www.ecp6.jussieu.fr/pageperso/bondy/books/gtwa/gtwa.html 

Wikimedia Foundation. 2010.

Look at other dictionaries:

  • Tietze — Tietze: Tietze extension theorem Tietze s graph Tietze s syndrome, named after Alexander Tietze Tietze transformation in mathematics, named after Heinrich Tietze Tietze, Tieze as German surnames This disambiguation page lists articles associated… …   Wikipedia

  • Graphe de Tietze — Représentation du graphe de Tietze. Nombre de sommets 12 Nombre d arêtes 18 Distribution des degrés 3 régulier Rayon …   Wikipédia en Français

  • Cubic graph — Not to be confused with graphs of cubic functions. The Petersen graph is a Cubic graph …   Wikipedia

  • Cycle double cover — Unsolved problems in mathematics Does every bridgeless graph have a multiset of cycles covering every edge exactly twice? …   Wikipedia

  • Projet:Mathématiques/Liste des articles de mathématiques — Cette page n est plus mise à jour depuis l arrêt de DumZiBoT. Pour demander sa remise en service, faire une requête sur WP:RBOT Cette page recense les articles relatifs aux mathématiques, qui sont liés aux portails de mathématiques, géométrie ou… …   Wikipédia en Français

  • List of mathematics articles (T) — NOTOC T T duality T group T group (mathematics) T integration T norm T norm fuzzy logics T schema T square (fractal) T symmetry T table T theory T.C. Mits T1 space Table of bases Table of Clebsch Gordan coefficients Table of divisors Table of Lie …   Wikipedia

  • CW complex — In topology, a CW complex is a type of topological space introduced by J. H. C. Whitehead to meet the needs of homotopy theory. This class of spaces is broader and has some better categorical properties than simplicial complexes, but still… …   Wikipedia

  • List of theorems — This is a list of theorems, by Wikipedia page. See also *list of fundamental theorems *list of lemmas *list of conjectures *list of inequalities *list of mathematical proofs *list of misnamed theorems *Existence theorem *Classification of finite… …   Wikipedia

  • Liste mathematischer Sätze — Inhaltsverzeichnis A B C D E F G H I J K L M N O P Q R S T U V W X Y Z A Satz von Abel Ruffini: eine allgemeine Polynomgleichung vom …   Deutsch Wikipedia

  • Metric space — In mathematics, a metric space is a set where a notion of distance (called a metric) between elements of the set is defined. The metric space which most closely corresponds to our intuitive understanding of space is the 3 dimensional Euclidean… …   Wikipedia

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”