✦ LIBER ✦

Randomly antitraceable digraphs

✍ Scribed by John Frederick Fink

Publisher: John Wiley and Sons
Year: 1982
Tongue: English
Weight: 376 KB
Volume: 6
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.3190060412

No coin nor oath required. For personal study only.

✦ Synopsis

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 antitraceable digraphs are characterized.

📜 SIMILAR VOLUMES

Randomly antitraceable digraphs

✍ John Frederick Fink 📂 Article 📅 1983 🏛 John Wiley and Sons 🌐 English ⚖ 27 KB

Hypotraceable digraphs

✍ Martin Grötschel; Carsten Thomassen; Yoshiko Wakabayashi 📂 Article 📅 1980 🏛 John Wiley and Sons 🌐 English ⚖ 233 KB

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

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

✍ Robert W. Robinson 📂 Article 📅 1977 🏛 John Wiley and Sons 🌐 English ⚖ 94 KB

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

Randomly matchable graphs

✍ David P. Summer 📂 Article 📅 1979 🏛 John Wiley and Sons 🌐 English ⚖ 190 KB

## Abstract A graph is defined to be randomly matchable if every matching of __G__ can be extended to a perfect matching. It is shown that the connected randomly matchable graphs are precisely __K__~2__n__~ and __K~n,n~__ (__n__ ≥ 1).