Every graph occurs as an induced subgraph of some hypohamiltonian graph. (English) Zbl 1393.05095

Zamfirescu, Carol T.; Zamfirescu, Tudor I.

J. Graph Theory 88, No. 4, 551-557 (2018).

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.)

Keywords:

hypo-Hamiltonian graph; induced subgraph

Citations:

Zbl 0253.05142; Zbl 0286.05122; Zbl 0371.05015; Zbl 0367.05046