Geodesic
On Subtrees of Directed Graphs with No Path of Length Exceeding One
Canadian mathematical bulletin, Tome 13 (1970) no. 3, pp. 329-332

Voir la notice de l'article provenant de la source Cambridge

DOI

The following theorem was conjectured to hold by P. Erdös [1]:Theorem 1. For each finite directed tree T with no directed path of length 2, there exists a constant c(T) such that if G is any directed graph with n vertices and at least c(T)n edges and n is sufficiently large, then T is a subgraph of G. In this note we give a proof of this conjecture. In order to prove Theorem 1, we first need to establish the following weaker result. 
Graham, R. L. On Subtrees of Directed Graphs with No Path of Length Exceeding One. Canadian mathematical bulletin, Tome 13 (1970) no. 3, pp. 329-332. doi: 10.4153/CMB-1970-063-1
@article{10_4153_CMB_1970_063_1,
     author = {Graham, R. L.},
     title = {On {Subtrees} of {Directed} {Graphs} with {No} {Path} of {Length} {Exceeding} {One}},
     journal = {Canadian mathematical bulletin},
     pages = {329--332},
     year = {1970},
     volume = {13},
     number = {3},
     doi = {10.4153/CMB-1970-063-1},
     url = {http://geodesic.mathdoc.fr/articles/10.4153/CMB-1970-063-1/}
}
TY  - JOUR
AU  - Graham, R. L.
TI  - On Subtrees of Directed Graphs with No Path of Length Exceeding One
JO  - Canadian mathematical bulletin
PY  - 1970
SP  - 329
EP  - 332
VL  - 13
IS  - 3
UR  - http://geodesic.mathdoc.fr/articles/10.4153/CMB-1970-063-1/
DO  - 10.4153/CMB-1970-063-1
ID  - 10_4153_CMB_1970_063_1
ER  - 
%0 Journal Article
%A Graham, R. L.
%T On Subtrees of Directed Graphs with No Path of Length Exceeding One
%J Canadian mathematical bulletin
%D 1970
%P 329-332
%V 13
%N 3
%U http://geodesic.mathdoc.fr/articles/10.4153/CMB-1970-063-1/
%R 10.4153/CMB-1970-063-1
%F 10_4153_CMB_1970_063_1

Cité par Sources :