✦ LIBER ✦

Short cycles in digraphs

✍ Scribed by Tsuyoshi Nishimura

Publisher: Elsevier Science
Year: 1988
Tongue: English
Weight: 188 KB
Volume: 72
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(88)90219-1

No coin nor oath required. For personal study only.

✦ Synopsis

Caccetta and Haggkvist [l] conjectured that every digraph with n vertices and minimum outdegree k contains a directed cycle of length at most [n/k]. With regard to this conjecture, Chvatal and Szemeredi [2] proved that if G is a digraph with n vertices and if each of these vertices has outdegree at least k, then G contains a cycle of length at most (n/k) + 2500.

Our result is an improvement of this result.

📜 SIMILAR VOLUMES

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.

On cycles and paths in digraphs

✍ M.C. Heydemann 📂 Article 📅 1980 🏛 Elsevier Science 🌐 English ⚖ 273 KB

The purpose of this communication is to announce some slrfficient conditions on degrees and number of arcs to insure the existence of cycles and paths in directed graphs. We show that these results are the best possible. The proofs of the theorems can be found in [4].

On digraphs without antidirected cycles

✍ Douglas D. Grant; F. Jaeger; C. Payan 📂 Article 📅 1982 🏛 John Wiley and Sons 🌐 English ⚖ 259 KB

## Abstract Let __t__(__n__) denote the greatest number of arcs in a diagraph of orders __n__ which does not contain any antidrected cycles. We show that [16/5(__n__ − 1)] ≤ __t__(__n__) ≤ 1/2 (__n__ − 1) for n ≥ 5. Let __t~r~__ (__n__) denote the corresponding quantity for __r__‐colorable digraphs

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.

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.

On complementary cycles in locally semic

On complementary cycles in locally semicomplete digraphs

✍ Yubao Guo; Lutz Volkmann 📂 Article 📅 1994 🏛 Elsevier Science 🌐 English ⚖ 440 KB

In this paper we show that a 2-connected locally semicomplete digraph of order at least 8 is not cycle complementary if and only if it is 2-diregular and has odd order. This result yields immediately two conjectures of Bang-Jensen.