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


05C38 Paths and cycles
05C45 Eulerian and Hamiltonian graphs


Zbl 1359.05072
Full Text: DOI Link