×

zbMATH — the first resource for mathematics

Every graph occurs as an induced subgraph of some hypohamiltonian graph. (English) Zbl 1393.05095
Summary: We prove the titular statement. This settles a problem of V. Chvatal [Can. Math. Bull. 16, 33–41 (1973; Zbl 0253.05142)] and encompasses earlier results of C. Thomassen [Discrete Math. 10, 383–390 (1974; Zbl 0286.05122); Lect. Notes Math. 642, 557–571 (1978; Zbl 0371.05015)], who showed it for \(K_{3}\), and J. B. Collier and E. F. Schmeichel [Discrete Math. 18, 265–271 (1977; Zbl 0367.05046)], who proved it for bipartite graphs. We also show that for every outerplanar graph there exists a planar hypohamiltonian graph containing it as an induced subgraph.

MSC:
05C10 Planar graphs; geometric and topological aspects of graph theory
05C45 Eulerian and Hamiltonian graphs
05C60 Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.)
PDF BibTeX XML Cite
Full Text: DOI