# zbMATH — the first resource for mathematics

On non-Hamiltonian graphs for which every vertex-deleted subgraph is traceable. (English) Zbl 1370.05115
Summary: We call a graph $$G$$ a platypus if $$G$$ is non-Hamiltonian, and for any vertex $$v$$ in $$G$$, the graph $$G-v$$ is traceable. Every hypo-Hamiltonian and every hypotraceable graph is a platypus, but there exist platypuses that are neither hypo-Hamiltonian nor hypotraceable. Among other things, we give a sharp lower bound on the size of a platypus depending on its order, draw connections to other families of graphs, and solve two open problems of G. Wiener [ibid. 84, No. 4, 443–459 (2017; Zbl 1359.05072)]. We also prove that there exists a $$k$$-connected platypus for every $$k\geq 2$$.

##### MSC:
 05C38 Paths and cycles 05C45 Eulerian and Hamiltonian graphs
Full Text: