𝔖 Bobbio Scriptorium
✦   LIBER   ✦

A note on subdigraphs of digraphs with large outdegrees

✍ Scribed by Noga Alon

Publisher
Elsevier Science
Year
1984
Tongue
English
Weight
67 KB
Volume
49
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

✦ Synopsis

In his survey article [3] Nash Williams gives a list of unsolved problems. The last problem is the following.

Let an (n, ~>q)-digraph denote a digraph without loops and parallel directed edges on a set of n vertices such that the outdegree of every vertex is at least q. If D is an (m + n, >~q + r)-digraph, must there be some subdigraph of D which is an (m, ~>q) or an (n, ~>r) digraph?

The following proposition shows that the answer is "No" even if we allow a somewhat weaker conclusion.

πŸ“œ SIMILAR VOLUMES

A note on complete subdivisions in digra
A note on complete subdivisions in digraphs of large outdegree
✍ Daniela KΓΌhn; Deryk Osthus; Andrew Young πŸ“‚ Article πŸ“… 2007 πŸ› John Wiley and Sons 🌐 English βš– 109 KB πŸ‘ 1 views

## Abstract Mader conjectured that for all $\ell$ there is an integer $\delta^+(\ell)$ such that every digraph of minimum outdegree at least $\delta^+(\ell)$ contains a subdivision of a transitive tournament of order $\ell$. In this note, we observe that if the minimum outdegree of a digraph is suf

On strong digraphs with a unique minimal
On strong digraphs with a unique minimally strong subdigraph
✍ Richard A. Brualdi; Rachel Manber πŸ“‚ Article πŸ“… 1988 πŸ› Elsevier Science 🌐 English βš– 659 KB

In this paper we determine the maximum number of &ges that a strong digraph can have if it has a unique minimally stroug subdigraph. We show that this number equais lrils = I)/2 + 1. Furthermore we show that there is, &to an isomorphism, a unique strong &graph which attains this maximum.