𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On planar hypohamiltonian graphs

✍ Scribed by Gábor Wiener; Makoto Araya

Publisher
John Wiley and Sons
Year
2010
Tongue
English
Weight
144 KB
Volume
67
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

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.

📜 SIMILAR VOLUMES

A planar hypohamiltonian graph with 48 v
A planar hypohamiltonian graph with 48 vertices
✍ Carol T. Zamfirescu; Tudor I. Zamfirescu 📂 Article 📅 2007 🏛 John Wiley and Sons 🌐 English ⚖ 123 KB

## Abstract We present a planar hypohamiltonian graph on 48 vertices, and derive some consequences. © 2007 Wiley Periodicals, Inc. J Graph Theory 55: 338–342, 2007

On paths in planar graphs
On paths in planar graphs
✍ Sanders, Daniel P. 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 93 KB 👁 2 views

This paper generalizes a theorem of Thomassen on paths in planar graphs. As a corollary, it is shown that every 4-connected planar graph has a Hamilton path between any two specified vertices x, y and containing any specified edge other than xy.

Antisymmetric flows on planar graphs
Antisymmetric flows on planar graphs
✍ T. H. Marshall 📂 Article 📅 2006 🏛 John Wiley and Sons 🌐 English ⚖ 104 KB

## Abstract We prove that every oriented planar graph admits a homomorphism to the Paley tournament __P__~271~ and hence that every oriented planar graph has an antisymmetric flow number and a strong oriented chromatic number of at most 271. © 2006 Wiley Periodicals, Inc. J Graph Theory 52: 200–210

On the linear arboricity of planar graph
On the linear arboricity of planar graphs
✍ Wu, Jian-Liang 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 188 KB 👁 2 views

The linear arboricity la(G) of a graph G is the minimum number of linear forests that partition the edges of G. Akiyama, Exoo, and Harary conjectured for any simple graph G with maximum degree ∆. The conjecture has been proved to be true for graphs having ∆ =

On certain Hamiltonian cycles in planar
On certain Hamiltonian cycles in planar graphs
✍ B�hme, T.; Harant, J.; Tk�?, M. 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 162 KB 👁 2 views

The problem is considered under which conditions a 4-connected planar or projective planar graph has a Hamiltonian cycle containing certain prescribed edges and missing certain forbidden edges. The results are applied to obtain novel lower bounds on the number of distinct Hamiltonian cycles that mus