Published January 1, 2011
| Version v1
Journal article
Open
On Planar Hypohamiltonian Graphs
Creators
- 1. Budapest Univ Technol & Econ, Dept Comp Sci & Informat Theory, H-1117 Budapest, Hungary
- 2. Shizuoka Univ, Dept Comp Sci, Hamamatsu, Shizuoka 4328011, Japan
Description
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
Files
bib-dc8bab08-ac9f-45a1-b18f-b6f4b99f5670.txt
Files
(103 Bytes)
| Name | Size | Download all |
|---|---|---|
|
md5:b025e8be5fa6785b73f4b8053ac1a7cd
|
103 Bytes | Preview Download |