Hamilton cycles in prisms

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 examin...

Full description

Saved in:
Bibliographic Details
Published in:Journal of graph theory 2007-12, Vol.56 (4), p.249-269
Main Authors: Kaiser, Tomáš, Ryjáček, Zdeněk, Král, Daniel, Rosenfeld, Moshe, Voss, Heinz-Jürgen
Format: Article
Language:English
Subjects:
graph prisms
Hamilton cycles
line graphs
planar graphs
toughness
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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
ISSN:0364-9024
1097-0118
DOI:10.1002/jgt.20250