Dergi makalesi Açık Erişim

On Planar Hypohamiltonian Graphs

2011    Wiener, Gabor; Araya, Makoto

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. (C) 2010 Wiley Periodicals, Inc. J Graph Theory 67: 55-68, 2011