✦ LIBER ✦

Prism-hamiltonicity of triangulations

✍ Scribed by Daniel P. Biebighauser; M. N. Ellingham

Publisher: John Wiley and Sons
Year: 2008
Tongue: English
Weight: 226 KB
Volume: 57
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.20276

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

📜 SIMILAR VOLUMES

Hamilton cycles in prisms

✍ Tomáš Kaiser; Zdeněk Ryjáček; Daniel Král; Moshe Rosenfeld; Heinz-Jürgen Voss 📂 Article 📅 2007 🏛 John Wiley and Sons 🌐 English ⚖ 300 KB

## 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 relaxati

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

Prism

✍ Austin, Harley 📂 Fiction 📅 2019 🌐 English ⚖ 147 KB 👁 1 views

Prism

✍ Shepard, Ashley 📂 Fiction 📅 2019 🌐 English ⚖ 226 KB

Expansion of Centered Triangulations

✍ D. Benard; J.L. Fouquet 📂 Article 📅 1994 🏛 Elsevier Science 🌐 English ⚖ 370 KB

We use a construction of A. Bouchet for covering triangulations by means of nowhere-zero dual flows, but slightly modified, to prove that whenever \(G\) is a simple graph, which is not a star, two-cell embedded in a surface \(S\), and \(m\) is a nonnegative integer not divisible by 2,3 , or 5 , ther

Irreducible Triangulations of Surfaces

✍ Z. Gao; R.B. Richter; P.D. Seymour 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 346 KB

In this note we show that, for any surface 7 and any k, there are at most finitely many triangulations of 7 such that each edge is in a noncontractible cycle of length k and is in no shorter noncontractible cycle. Such a triangulation is k-irreducible. This is equivalent to the statement that for an