A graph G is hypohamiltonian if G is nonhamiltonian, but G - v is Hamiltonian for every v element V. The Petersen graph, which has ten nodes, is the smallest hypohamiltonian graph and the only such graph on ten nodes. Herz et al. (1967) showed that there are no hypohamiltonian graphs with 11 or 12 vertices. By parity, no bipartite graph is hypohamiltonian. Many (but not all) snarks are hypohamiltonian. Hypohamiltonian graphs are almost Hamiltonian. Zamfirescu showed that every singlecross hypohamiltonian graph contains a cubic vertex.
almost Hamiltonian graph | almost hypohamiltonian graph | Araya-Wiener graphs | cubic planar hypohamiltonian graph | Hamiltonian graph | Hatzel graph | hypotraceable graph | lindgren-sousselier graph | Petersen graph | planar hypohamiltonian graph | snark | traceable graph | Wiener-Araya graph | Zamfirescu graphs
We guarantee you’ll find the right tutor, or we’ll cover the first hour of your lesson.