Paper Info
Title
On almost hypohamiltonian graphs.
Abstract
A graph G is almost hypohamiltonian (a.h.) if G is non-hamiltonian, there exists a vertex w in G such that G - v is non-hamiltonian, and G - v is hamiltonian for every vertex v not equal w in G. The second author asked in [J. Graph Theory 79 (2015) 63-81] for all orders for which a.h. graphs exist. Here we solve this problem. To this end, we present a specialised algorithm which generates complete sets of a.h. graphs for various orders. Furthermore, we show that the smallest cubic a.h. graphs have order 26. We provide a lower bound for the order of the smallest planar a.h. graph and improve the upper bound for the order of the smallest planar a.h. graph containing a cubic vertex. We also determine the smallest planar a.h. graphs of girth 5, both in the general and cubic case. Finally, we extend a result of Steffen on snarks and improve two bounds on longest paths and longest cycles in polyhedral graphs due to Jooyandeh, McKay, Ostergard, Pettersson, and the second author.
Year
Venue
Keywords
2019
DISCRETE MATHEMATICS AND THEORETICAL COMPUTER SCIENCE
hamiltonian,hypohamiltonian,almost hypohamiltonian,planar,cubic,exhaustive generation
Field
DocType
Volume
Graph theory,Discrete mathematics,Graph,Combinatorics,Vertex (geometry),Hamiltonian (quantum mechanics),Existential quantification,Upper and lower bounds,Planar,Mathematics
Journal
21.0
Issue
ISSN
Citations 
4.0
1462-7264
0
PageRank 
References 
Authors
0.34
0
2
Name
Order
Citations
PageRank
Jan Goedgebeur19718.05
Carol T. Zamfirescu23815.25