Tietze's Graph

 

Tietze's graph is the cubic graph on 12 nodes and 18 edges illustrated above in a number of embeddings.

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

Tietze's 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).

Tietze's graph provides a 6-color coloring of the Möbius strip as illustrated above.

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

---

REFERENCES

Bondy, J. A. and Murty, U. S. R. Graph Theory with Applications. New York: North Holland, p. 243, 1976.

Clark, L. and Entringer, R. "Smallest Maximally Nonhamiltonian Graphs." Periodica Math. Hungarica 14, 57-68, 1983.

Punnim, N.; Saenpholphat, V.; and Thaithae, S. "Almost Hamiltonian Cubic Graphs." Int. J. Comput. Sci. Netw. Security 7, 83-86, 2007.

مواضيع ذات صلة

Minimum Spanning Tree

Maximum Leaf Number

Lobster Graph

Labeled Tree

Internal Path Length

Red-Black Tree

Pseudotree

Pseudoforest

Prüfer Code

Planted Tree

Planted Planar Tree

Graph Strength