𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Orientations of hamiltonian cycles in large digraphs

✍ Scribed by Adam Paweł Wojda

Publisher
John Wiley and Sons
Year
1986
Tongue
English
Weight
328 KB
Volume
10
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

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.

📜 SIMILAR VOLUMES

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.

Oriented Hamiltonian Cycles in Tournamen
Oriented Hamiltonian Cycles in Tournaments
✍ Frédéric Havet 📂 Article 📅 2000 🏛 Elsevier Science 🌐 English ⚖ 379 KB

We prove that every tournament of order n 68 contains every oriented Hamiltonian cycle except possibly the directed one when the tournament is reducible.

Cycles through Large Degree Vertices in
Cycles through Large Degree Vertices in Digraphs: A Generalization of Meyniel's Theorem
✍ Kenneth A. Berman; Xin Liu 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 191 KB

Let D=(V, E) be a digraph with vertex set V of size n and arc set E. For u # V, let d(u) denote the degree of u. A Meyniel set M is a subset of V such that d(u)+d(v) 2n&1 for every pair of nonadjacent vertices u and v belonging to M. In this paper we show that if D is strongly connected, then every

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.