𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Hamilton cycles in prisms

✍ Scribed by Tomáš Kaiser; Zdeněk Ryjáček; Daniel Král; Moshe Rosenfeld; Heinz-Jürgen Voss

Publisher
John Wiley and Sons
Year
2007
Tongue
English
Weight
300 KB
Volume
56
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

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

📜 SIMILAR VOLUMES

Prism-hamiltonicity of triangulations
Prism-hamiltonicity of triangulations
✍ Daniel P. Biebighauser; M. N. Ellingham 📂 Article 📅 2008 🏛 John Wiley and Sons 🌐 English ⚖ 226 KB

## Abstract The __prism__ over a graph __G__ is the Cartesian product __G__ □ __K__~2~ of __G__ with the complete graph __K__~2~. 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

Oriented hamilton cycles in digraphs
Oriented hamilton cycles in digraphs
✍ Roland Häggkvist; Andrew Thomason 📂 Article 📅 1995 🏛 John Wiley and Sons 🌐 English ⚖ 473 KB

## Abstract We show that a directed graph of order __n__ will contain __n__‐cycles of every orientation, provided each vertex has indegree and outdegree at least (1/2 + __n__^‐1/6^)__n__ and __n__ is sufficiently large. © 1995 John Wiley & Sons, Inc.

Hamilton cycles in plane triangulations
Hamilton cycles in plane triangulations
✍ Bill Jackson; Xingxing Yu 📂 Article 📅 2002 🏛 John Wiley and Sons 🌐 English ⚖ 134 KB

## Abstract We extend Whitney's Theorem that every plane triangulation without separating triangles is hamiltonian by allowing some separating triangles. More precisely, we define a decomposition of a plane triangulation __G__ into 4‐connected ‘pieces,’ and show that if each piece shares a triangle

Hamilton cycles in regular graphs
Hamilton cycles in regular graphs
✍ Bill Jackson 📂 Article 📅 1978 🏛 John Wiley and Sons 🌐 English ⚖ 135 KB

## UNIVERSIW OF WATERLOO ' The research reported here has been sponsored by the Canadian Commonwealth Association.