Premium
Hamilton cycles in prisms
Author(s) -
Kaiser Tomáš,
Ryjáček Zdeněk,
Král Daniel,
Rosenfeld Moshe,
Voss HeinzJürgen
Publication year - 2007
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.20250
Subject(s) - mathematics , cartesian product , converse , hamiltonian (control theory) , combinatorics , hamiltonian path , quartic graph , graph , cartesian coordinate system , prism , discrete mathematics , graph power , geometry , physics , line graph , optics , mathematical optimization
The prism over a graph G is the Cartesian product G □ K 2 of G with the complete graph K 2 . If G is hamiltonian, then G □ K 2 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