Prism‐hamiltonicity of triangulations |
| |
Authors: | Daniel P Biebighauser M N Ellingham |
| |
Institution: | 1. Department of Mathematics, 1326 Stevenson Center, Vanderbilt University, Nashville, Tennessee 37240;2. Department of Mathematics and Computer Science, Concordia College, 901 8th Street S., Moorhead, Minnesota 56562 |
| |
Abstract: | The prism over a graph G is the Cartesian product G □ K2 of G with the complete graph K2. If the prism over G is hamiltonian, we say that G is prism‐hamiltonian. We prove that triangulations of the plane, projective plane, torus, and Klein bottle are prism‐hamiltonian. We additionally show that every 4‐connected triangulation of a surface with sufficiently large representativity is prism‐hamiltonian, and that every 3‐connected planar bipartite graph is prism‐hamiltonian. © 2007 Wiley Periodicals, Inc. J Graph Theory 57: 181–197, 2008 |
| |
Keywords: | hamilton cycle prism planar graph |
|
|