✦ LIBER ✦

Oriented hamilton cycles in digraphs

✍ Scribed by Roland Häggkvist; Andrew Thomason

Publisher: John Wiley and Sons
Year: 1995
Tongue: English
Weight: 473 KB
Volume: 19
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.3190190404

No coin nor oath required. For personal study only.

✦ Synopsis

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.

📜 SIMILAR VOLUMES

Orientations of hamiltonian cycles in la

Orientations of hamiltonian cycles in large digraphs

✍ Adam Paweł Wojda 📂 Article 📅 1986 🏛 John Wiley and Sons 🌐 English ⚖ 328 KB

We prove that, with some exceptions, every digraph with n 3 9 vertices and at least ( n -1) ( n -2) + 2 arcs contains all orientations of a Hamiltonian cycle.

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

Hamiltonicity and reversing arcs in digr

Hamiltonicity and reversing arcs in digraphs

✍ Klostermeyer, William F.; S?olt�s, L?ubom�r 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 282 KB

In this paper we introduce a new hamiltonian-like property of graphs. A graph G is said to be cyclable if for each orientation D of G there is a set S of vertices such that reversing all the arcs of D with one end in S results in a hamiltonian digraph. We characterize cyclable complete multipartite

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

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

Cycles of Prescribed Modularity in Plana

Cycles of Prescribed Modularity in Planar Digraphs

✍ Anna Galluccio; Martin Loebl 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 252 KB

We present a polynomial-time algorithm to find out whether all directed cycles in a directed planar graph are of length p mod q, with 0 F pq.