On Hypohamiltonian and Almost Hypohamiltonian Graphs |
| |
Authors: | Carol T Zamfirescu |
| |
Institution: | FAKULT?T FüR MATHEMATIK, TECHNISCHE UNIVERSIT?T DORTMUND, GERMANY |
| |
Abstract: | A graph G is almost hypohamiltonian if G is non‐hamiltonian, there exists a vertex w such that is non‐hamiltonian, and for any vertex the graph is hamiltonian. We prove the existence of an almost hypohamiltonian graph with 17 vertices and of a planar such graph with 39 vertices. Moreover, we find a 4‐connected almost hypohamiltonian graph, while Thomassen's question whether 4‐connected hypohamiltonian graphs exist remains open. We construct planar almost hypohamiltonian graphs of order n for every . During our investigation we draw connections between hypotraceable, hypohamiltonian, and almost hypohamiltonian graphs, and discuss a natural extension of almost hypohamiltonicity. Finally, we give a short argument disproving a conjecture of Chvátal (originally disproved by Thomassen), strengthen a result of Araya and Wiener on cubic planar hypohamiltonian graphs, and mention open problems. |
| |
Keywords: | Grinberg's Criterion hypohamiltonian planar 05C10 05C38 05C45 |
|
|