Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4649399 | Discrete Mathematics | 2010 | 4 Pages |
Abstract
In 1956, W.T. Tutte proved that every 4-connected planar graph is hamiltonian. Moreover, in 1997, D.P. Sanders extended this to the result that a 4-connected planar graph contains a hamiltonian cycle through any two of its edges. It is shown that Sanders’ result is best possible by constructing 4-connected maximal planar graphs with three edges a large distance apart such that any hamiltonian cycle misses one of them. If the maximal planar graph is 5-connected then such a construction is impossible.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
F. Göring, J. Harant,