zbMATH — the first resource for mathematics

Seven problems on hypohamiltonian and almost hypohamiltonian graphs. (English) Zbl 1376.05081
Adiprasito, Karim (ed.) et al., Convexity and discrete geometry including graph theory. Mulhouse, France, September 1–11, 2014. Cham: Springer (ISBN 978-3-319-28184-1/hbk; 978-3-319-28186-5/ebook). Springer Proceedings in Mathematics & Statistics 148, 253-255 (2016).
The author, a well-known researcher of hypohamiltonian graphs, almost hypohamiltonian graphs, hypotraceable graphs and almost hypotraceable graphs, presents seven groups of open problems for these classes of graph. For example, the order of the smallest known planar hypohamiltonian graph is 40, while the best known lower bound on the order of such graphs is 18.
Problems: (a) Are there planar hypohamiltonian graphs of order less than 40?
(b) What is the smallest integer \(n_0\) such that there exists a planar hypohamiltonian graph for every integer \(n\geq n_0\)?
These seven groups of problems, and the included discussions, give the reader a very good sense of what is known, what the experts are asking and “why”?
There is, one should note, an issue with the numbering label of problem \(\#\)3 that is somewhat confusing.
For the entire collection see [Zbl 1348.52001].

05C45 Eulerian and Hamiltonian graphs
05C38 Paths and cycles
05C10 Planar graphs; geometric and topological aspects of graph theory
Full Text: DOI