Hamilton cycles in prisms |
| |
| Authors: | Tomá? Kaiser Zdeněk Ryjá?ek Daniel Král Moshe Rosenfeld Heinz‐Jürgen Voss |
| |
| Institution: | 1. Department of Mathematics, University of West Bohemia and Institute for Theoretical Computer Science (ITI), Univerzitní 8, 306 14 Plzencaron;2. Czech Republic;3. Institute for Theoretical Computer Science (ITI) and Faculty of Mathematics and Physics, Charles University, Malostranské Náměstí 25, 118 00 Prague, Czech Republic;4. Computing and Software Systems Program, University of Washington, Tacoma, Washington 98402;5. Institute of Algebra, Technical University Dresden, Mommsenstrasse 13, D‐01062 Dresden, Germany;6. Sadly, the last author passed away in September 2003. |
| |
| Abstract: | The prism over a graph G is the Cartesian product G □ K2 of G with the complete graph K2. If G is hamiltonian, then G□K2 is also hamiltonian but the converse does not hold in general. Having a hamiltonian prism is shown to be an interesting relaxation of being hamiltonian. In this article, we examine classical problems on hamiltonicity of graphs in the context of having a hamiltonian prism. © 2007 Wiley Periodicals, Inc. J Graph Theory 56: 249–269, 2007 |
| |
| Keywords: | Hamilton cycles graph prisms planar graphs line graphs toughness |
|
|
