TOPICS
Search

Tietze Graph

DOWNLOAD Mathematica NotebookDownload Wolfram Notebook
TietzesGraphEmbeddings

The Tietze graph is the cubic graph on 12 nodes and 18 edges, illustrated above in a number of drawings.

The Tietze graph is the twisted Isaacs graph FS(2,3), obtained by closing a chain of three claw graphs with a transposition (Nedela and Škoviera 2022).

It is implemented in the Wolfram Language as GraphData["TietzeGraph"].

The Tietze graph is the unique almost Hamiltonian cubic graph on 12 vertices (Punnim et al. 2007). In fact, it is also maximally nonhamiltonian (Clark and Entringer 1983) and a platypus graph.

TietzeMoebiusColoring

The Tietze graph provides a 6-color graph coloring of the Möbius strip as illustrated above (Bondy and Murty 1976, p. 243).

TietzeGraphMatrices

The plots above show the adjacency matrix, incidence matrix, and graph distance matrices for the Tietze graph.

See also

Cubic Graph, Möbius Strip

Explore with Wolfram|Alpha

References

Bondy, J. A. and Murty, U. S. R. Graph Theory with Applications. New York: North Holland, p. 243, 1976.Bondy, J. A. and Murty, U. S. R. Graph Theory. Berlin, Germany: Springer-Verlag, p. 394, 2008.Clark, L. and Entringer, R. "Smallest Maximally Nonhamiltonian Graphs." Periodica Math. Hungarica 14, 57-68, 1983.Goedgebeur, J.; Neyt, A.; and Zamfirescu, C. T. "Structural and Computational Results on Platypus Graphs." Appl. Math. Comput. 386, 125491, 2020.House of Graphs. "Tietzes Graph." https://houseofgraphs.org/graphs/1368.Nedela, R. and Škoviera, M. "Cyclic Connectivity, Edge-Elimination, and the Twisted Isaacs Graphs." J. Combin. Th. Ser. B 155, 17-44, 2022. https://doi.org/10.1016/j.jctb.2022.01.007.Punnim, N.; Saenpholphat, V.; and Thaithae, S. "Almost Hamiltonian Cubic Graphs." Int. J. Comput. Sci. Netw. Security 7, 83-86, 2007.

Cite this as:

Weisstein, Eric W. "Tietze Graph." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/TietzeGraph.html

Subject classifications