Name
Abstract | ||
|---|---|---|
A graph G is almost hypohamiltonian if G is non-hamiltonian, there exists a vertex w such that G-w is non-hamiltonian, and for any vertex v﾿w the graph G-v 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 n﾿74. 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. |
Year | DOI | Venue |
|---|---|---|
2015 | 10.1002/jgt.21815 | Journal of Graph Theory |
Keywords | Field | DocType |
planar | Grinberg's theorem,Topology,Discrete mathematics,Graph,Combinatorics,Hamiltonian (quantum mechanics),Vertex (geometry),Existential quantification,Hypohamiltonian graph,Conjecture,Mathematics | Journal |
Volume | Issue | ISSN |
79 | 1 | 0364-9024 |
Citations | PageRank | References |
2 | 0.46 | 8 |
Authors | ||
1 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Carol T. Zamfirescu | 1 | 38 | 15.25 |