On non-Hamiltonian graphs for which every vertex-deleted subgraph is traceable. (English) Zbl 1370.05115

Zamfirescu, Carol T.

J. Graph Theory 86, No. 2, 223-243 (2017).

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

Keywords:

non-Hamiltonian graph; traceable graph; hypo-Hamiltonian graph; hypotraceable graph

Citations:

Zbl 1359.05072