𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Hypotraceable digraphs

✍ Scribed by Martin Grötschel; Carsten Thomassen; Yoshiko Wakabayashi

Publisher
John Wiley and Sons
Year
1980
Tongue
English
Weight
233 KB
Volume
4
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

A hypotraceable digraph is a digraph D = (V, E) which is not traceable, i.e., does not contain a (directed)Hamiltonian path, but for which D ‐ v is traceable for all ve ∈ V. We prove that a hypotraceable digraph of order n exists iff n ≥ 7 and that for each k ≥ 3 there are infinitely many hypotraceable oriented graphs with a source and a sink and precisely k strong components. We also show that there are strongly connected hypotraceable oriented graphs and that there are hypotraceable digraphs with precisely two strong components one of which is a source or a sink. Finally, we prove that hypo‐Hamiltonian and hypotraceable digraphs may contain large complete subdigraphs.

📜 SIMILAR VOLUMES

Girth in digraphs
Girth in digraphs
✍ J. C. Bermond; A. Germa; M. C. Heydemann; D. Sotteau 📂 Article 📅 1980 🏛 John Wiley and Sons 🌐 English ⚖ 211 KB

## Abstract For an integer __k__ > 2, the best function __m__(__n, k__) is determined such that every strong digraph of order __n__ with at least __m__(__n, k__) arcs contains a circuit of length __k__ or less.

Counting strong digraphs
Counting strong digraphs
✍ Robert W. Robinson 📂 Article 📅 1977 🏛 John Wiley and Sons 🌐 English ⚖ 94 KB
Randomly antitraceable digraphs
Randomly antitraceable digraphs
✍ John Frederick Fink 📂 Article 📅 1982 🏛 John Wiley and Sons 🌐 English ⚖ 376 KB

## Abstract An __antipath__ in a digraph is a semipath containing no (directed) path of length 2. A digraph __D__ is __randomly antitraceable__ if for each vertex __v__ of __D__, any antipath beginning at __v__ can be extended to a hamiltonian antipath beginning at __v.__ In this paper randomly ant

Superpure digraph designs
Superpure digraph designs
✍ Sven Hartmann 📂 Article 📅 2002 🏛 John Wiley and Sons 🌐 English ⚖ 174 KB

## Abstract A digraph design is a decomposition of a complete (symmetric) digraph into copies of pre‐specified digraphs. Well‐known examples for digraph designs are Mendelsohn designs, directed designs or orthogonal directed covers. A digraph design is superpure if any two of the subdigraphs in the