On planar hypohamiltonian graphs |
| |
| Authors: | Gábor Wiener Makoto Araya |
| |
| Affiliation: | 1. Department of Computer Science and Information Theory Budapest University of Technology and Economics 1117 Budapest, Magyar Tudósok K?rútja 2, Hungary;2. Department of Computer Science Shizuoka University Hamamatsu 432‐8011, Japan |
| |
| Abstract: | We present a planar hypohamiltonian graph on 42 vertices and (as a corollary) a planar hypotraceable graph on 162 vertices, improving the bounds of Zamfirescu and Zamfirescu and show some other consequences. We also settle the open problem whether there exists a positive integer N, such that for every integer n≥N there exists a planar hypohamiltonian/hypotraceable graph on n vertices. © 2010 Wiley Periodicals, Inc. J Graph Theory 67: 55‐68, 2011 |
| |
| Keywords: | graph Hamiltonian hypohamiltonian hypotraceable |
|
|
