Antidirected Subtrees of Directed Graphs

Burr, Stefan A.

Canadian mathematical bulletin, Tome 25 (1982) no. 1, pp. 119-120

Résumé

The purpose of this paper is to prove the following result: Theorem. Let T be a directed tree with k arcs and with no directed path of length 2. Then if G is any directed graph with n points and at least 4kn arcs, T is a subgraph of G.It would be appropriate to call T an antidirected tree or a source-sink tree, since every point either has all its arcs directed outward or all inward. As N. G. de Bruijn has noted (personal communication), such a linear bound in n cannot hold if T is replaced by any directed graph other than a union of such trees. The above theorem strengthens one of Graham [1], where an implicit bound of c(k)n is obtained, where c(k) is exponentially large. The proof we give here is also shorter. We first give two simple lemmas. Both are essentially due to ErdÄs, but it is not clear where either first appeared. Their proofs are easy, so we give them here for completeness; in neither case do we state quite the best possible result.

Détail

DOI : 10.4153/CMB-1982-017-4